Index for fast retrieval of uncertain spatial point data

ABSTRACT

Location information gathered from a variety of sources in the form of sensor data, video streams, human observations, and so on, is often imprecise and uncertain and needs to be represented approximately. To represent such uncertain location information, the use of a probabilistic model that captures the imprecise location as a probability density function (pdf) has been recently proposed. The pdfs can be arbitrarily complex depending on the type of application and the source of imprecision. Hence, efficiently representing, storing and querying pdfs is a very challenging task. While the current state of the art indexing approaches treat the representation and storage of pdfs as a black box, in this paper, we take the challenge of representing and storing any complex pdf in an efficient way. We further develop techniques to index such pdfs to support the efficient processing of location queries. Our extensive experiments demonstrate that our indexing techniques significantly outperform the best existing solutions.

REFERENCES

• 1: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 2: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Evaluating probabilistic queries over imprecise data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872823]
• 3: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Querying Imprecise Data in Moving Object Environments, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1112-1127, September 2004 [doi>10.1109/TKDE.2004.46]
• 4: R. Cheng, D. V. Kalashnikov, and S. Prabhakar. Evaluation of probabilistic queries over imprecise data in constantly-evolving environments. Information Systems Journal, 2006. to appear.
• 5: R. Cheng, S. Prabhakar, and D. V. Kalashnikov. Querying imprecise data in moving object environments. In ICDE, 2003.
• 6: R. Cheng, Y. Xia, S. Prabhakar, R. Shah, and J. S. Vitter. Efficient indexing methods for probabilistic threshold queries over uncertain data. In Proc. of VLDB, 2004.
• 7: Dmitri V. Kalashnikov , Yiming Ma , Sharad Mehrotra , Ramaswamy Hariharan , Carter Butts, Modeling and querying uncertain spatial information for situational awareness applications, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183471.1183494]
• 8: D. V. Kalashnikov, Y. Ma, S. Mehrotra, R. Hariharan, N. Venkatasubramanian, and N. Ashish. SAT: Spatial Awareness from Textual input. In Proc. of EDBT, 2006.
• 9: Dmitri V. Kalashnikov , Sunil Prabhakar , Susanne E. Hambrusch, Main Memory Evaluation of Monitoring Queries Over Moving Objects, Distributed and Parallel Databases, v.15 n.2, p.117-135, March 2004 [doi>10.1023/B:DAPD.0000013068.25976.88]
• 10: Dmitri V. Kalashnikov , Sunil Prabhakar , Susanne E. Hambrusch , Walid G. Aref, Efficient Evaluation of Continuous Range Queries on Moving Objects, Proceedings of the 13th International Conference on Database and Expert Systems Applications, p.731-740, September 02-06, 2002
• 11: Sharad Mehrotra , Carter Butts , Dmitri V. Kalashnikov , Nalini Venkatasubramanian , Kemal Altintas , Ram Hariharan , Haimin Lee , Yiming Ma , Amnon Myers , Jehan Wickramasuriya , Ron Eguchi , Charles Huyck, CAMAS: a citizen awareness system for crisis mitigation, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007718]
• 12: S. Mehrotra, C. Butts, D. V. Kalashnikov, N. Venkatasubramanian, R. Rao, G. Chockalingam, R. Eguchi, B. Adams, and C. Huyck. Project RESCUE: challenges in responding to the unexpected. SPIE, 5304:179--192, Jan. 2004.
• 13: Jürg Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multi-Key File Structure, Proceedings of the 3rd Conference of the European Cooperation in Informatics on Trends in Information Processing Systems, p.236-251, October 20-22, 1981
• 14: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 15: Yufei Tao , Reynold Cheng , Xiaokui Xiao , Wang Kay Ngai , Ben Kao , Sunil Prabhakar, Indexing multi-dimensional uncertain data with arbitrary probability density functions, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Performance

Keywords:
U-grid, probability, spatial database, uncertainty indexing