移动计算环境下非确定数据的索引与查询方法研究
|
摘要
在移动对象数据库的研究中，如何建模、索引并查询移动对象的位置信息是一个很重要的问题，学者们对此进行了大量研究，并提出了许多空间对象和时空对象的索引方法。但是传统的方法并不能支持此类数据的一个重要应用特性——非确定性，如何对非确定性数据进行查询处理成了数据库研究人员关注的焦点。在移动计算环境中，受限于测量设备误差，数据更新延迟，取样失真等因素，中心数据库很难全程记录移动对象的准确位置信息，鉴于传统的移动对象索引方法和查询处理技术均假设数据库中的数据是精确的，因此这些技术不能直接应用到非确定数据的索引和查询，或者效率极低，这就给研究者提出了新的问题和挑战。
U树是具有代表性的一种非确定对象空间索引方法，它是在R~*树基础之上融合了数据非确定性的变种。U树固有的良好动态结构，这使它不仅可以支持非确定数据对象以任何次序更新或插入，而且其提出的域查询处理算法不局限于非确定数据本身的概率密度分布函数。但U树本身只是针对非确定静止对象的索引，并不能支持非确定移动对象的索引或执行效率甚微。
基于移动计算环境，针对如何支持频繁位置更新的非确定移动对象当前及未来位置索引的问题，在基本U树结构上增加了记录移动对象非确定状态特征的数据结构，通过利用概率密度分布函数描述移动对象在非确定区域的位置分布，在保留原有位置记录的情况下加入时间特性，这样就可以预测移动对象在未来时间段内的大概位置信息，从而为当前及未来非确定位置信息检索提供可靠保证。在TPU树索引基础上，一种改进的基于p-bound的域查询处理算法MP_BBRQ，利用索引中记录的概率限定性区域和启发式判定准则，能高效的处理概率性域查询问题；一种基于分支定界思想的概率skyline查询处理算法B~2CPS，利用最近邻的最好优先遍历思想，能使查询处理的磁盘开销达到最优。
相对于传统的空间查询概念，非确定数据库中常用的查询——概率空间查询，由于其结果集中增加了结果正确性的保证系数，从而使得基于非确定数据的查询更具有可信性。鉴于概率空间查询具有很高的计算代价，需要进一步提高概率空间查询效率，尤其是旨在减少CPU计算时间和磁盘I／O次数的概率κ最近邻查询算法，国内外目前尚无相关研究。概率κ最近邻查询κ-PNN就是返回κ个非确定对象，而且这κ个非确定对象分别作为查询对象Q的第κ个最近邻居的概率，相对于其它非确定对象是最大的。与传统的κ最近邻查询相比，计算非确定对象的κ最近邻概率值需要原始的积分运算或Monte-Carlo方法，在这种情况下，概率κ最近邻查询的计算代价是非常高的。因此，必须尽量缩小查询所需搜索的空间范围，从而在不影响返回正确结果集的情况下，进一步减少所要考虑的非确定对象，在很大程度上避免利用原始计算公式来返回结果集。高效处理κ-PNN查询框架包含四个步骤：R树索引的建立，空间裁剪，概率裁剪和精炼阶段。利用安全可靠的空间裁剪以及概率裁剪方法，把这些方法与R树索引进行完美的结合以减少查询的搜索空间，从而提高κ-PNN查询的处理效率。实验结果表明，空间裁剪和概率裁剪方法具有非常高的裁剪效率，整个κ-PNN查询处理过程是可靠高效的。
非确定数据库需要研究的问题还很多，在许多查询问题上欠缺高效的处理算法，例如概率连接问题，概率Top-κ查询，概率反最近邻查询，以及概率反轮廓查询等等，因此，针对不同方面的概率空间和时空查询问题，将相应解决方法融入到数据库管理系统中以支持非确定数据的有效管理，将是研究人员面临的新问题。此外，将已有的研究成果应用于多维空间，并进一步考虑非欧式距离环境下的索引及查询处理方法可作为未来的研究方向。在非确定数据流环境下，如何利用有效的内存索引机制，提出各种高效的数据流查询算法也将是非常有潜力的研究课题。
One of the most important research issues in MOD is the problem of modeling andquerying the location of moving objects. Much work exists on traditional spatial andspatio-temporal queries, but there has recently attracted much research interest inevaluating such queries in the presence of uncertainty. This is reasonable, due to locationupdate delay, sampling error, or limitation of measuring equipments, it is rarely possiblefor the database to record the exact positions of moving objects at all times. Theconventional objects indexing methods and query processing techniques assume that thedata are precise, so they cannot be directly applied for uncertain data processing. As aresult, in the context of uncertain database, efficient indexing methods and correspondingquery processing techniques should be developed to guarantee the accuracy of answer andspeed up the query performance.
U-tree is currently the most popular indexing method for the imprecise positions ofstationary objects. It minimizes the amount of qualification probability computation inrange search and it's fully dynamic for the objects can be inserted or deleted in any order.However, it can not deal with the moving objects with uncertainty.
In the mobile environment, a spatio-temporal indexing structure TPU-tree, which is anovel U-tree based indexing technique, can combine the issues of timestamp to predict thefuture location of uncertain evolving data. Along with the data models capturing thespatial-temporal uncertainty and TPU-tree, a modified p-bound based range queryalgorithms (MP_BBRQ), using probabilistic pruning regions and corresponding decisionheuristic rules, can speed up the probabilistic range queries; and a branch and boundalgorithm for constrained probabilistic skyline (B~2CPS), using the best-first searchstrategy of nearest neighbor, can minimum the node access numbers.
New probabilistic spatial queries are more expensive to compute. The disk I/O- andcomputationally-efficient algorithms should be explored to enhance the performance ofprobabilistic range queries, probabilistic k nearest-neighbor queries. Specifically, aprobabilistic k nearest neighbor query returns k objects with the highest probability ofbeing the k-th nearest neighbor to a given query point Q. Comparedto the k-NN query intraditional databases, which retrieves k closest objects to the given query point, thecomputation cost of k-PNN is very expensive due to the costly numerical integration orMonte-Carlo approach it adopts. In order to speed up the k-PNN query processing,efficient spatial and probabilistic pruning approaches are used to reduce the search space,thus the costly numerical evaluation of complex integrals can be avoided as much aspossible. The Spatial and probabilistic pruning approaches can be seamless integrated inthe query procedure. Extensive experiments have been conducted to demonstrate theefficiency and effectiveness of algorithms under various parameter settings.
There are many research issues exist in the uncertain database. It would be interestingto apply new probabilistic queries techniques to solve new problems are explored, such asprobabilistic joins, probabilistic Top-k, probabilistic reverse nearest neighbors, andprobabilistic reverse skyline queries. For these kinds of probabilistic queries, how tointegrate these processing methods to DMBS will be new research issues. Furthermore,extend the current works to handle high dimensional data, and consider non-Euclideandistance could be another interesting directions. In the uncertain streaming environment,how to develop efficient memory indexing method, and speed up kind of streamingqueries will also be very potential research problems.
U树是具有代表性的一种非确定对象空间索引方法，它是在R~*树基础之上融合了数据非确定性的变种。U树固有的良好动态结构，这使它不仅可以支持非确定数据对象以任何次序更新或插入，而且其提出的域查询处理算法不局限于非确定数据本身的概率密度分布函数。但U树本身只是针对非确定静止对象的索引，并不能支持非确定移动对象的索引或执行效率甚微。
基于移动计算环境，针对如何支持频繁位置更新的非确定移动对象当前及未来位置索引的问题，在基本U树结构上增加了记录移动对象非确定状态特征的数据结构，通过利用概率密度分布函数描述移动对象在非确定区域的位置分布，在保留原有位置记录的情况下加入时间特性，这样就可以预测移动对象在未来时间段内的大概位置信息，从而为当前及未来非确定位置信息检索提供可靠保证。在TPU树索引基础上，一种改进的基于p-bound的域查询处理算法MP_BBRQ，利用索引中记录的概率限定性区域和启发式判定准则，能高效的处理概率性域查询问题；一种基于分支定界思想的概率skyline查询处理算法B~2CPS，利用最近邻的最好优先遍历思想，能使查询处理的磁盘开销达到最优。
相对于传统的空间查询概念，非确定数据库中常用的查询——概率空间查询，由于其结果集中增加了结果正确性的保证系数，从而使得基于非确定数据的查询更具有可信性。鉴于概率空间查询具有很高的计算代价，需要进一步提高概率空间查询效率，尤其是旨在减少CPU计算时间和磁盘I／O次数的概率κ最近邻查询算法，国内外目前尚无相关研究。概率κ最近邻查询κ-PNN就是返回κ个非确定对象，而且这κ个非确定对象分别作为查询对象Q的第κ个最近邻居的概率，相对于其它非确定对象是最大的。与传统的κ最近邻查询相比，计算非确定对象的κ最近邻概率值需要原始的积分运算或Monte-Carlo方法，在这种情况下，概率κ最近邻查询的计算代价是非常高的。因此，必须尽量缩小查询所需搜索的空间范围，从而在不影响返回正确结果集的情况下，进一步减少所要考虑的非确定对象，在很大程度上避免利用原始计算公式来返回结果集。高效处理κ-PNN查询框架包含四个步骤：R树索引的建立，空间裁剪，概率裁剪和精炼阶段。利用安全可靠的空间裁剪以及概率裁剪方法，把这些方法与R树索引进行完美的结合以减少查询的搜索空间，从而提高κ-PNN查询的处理效率。实验结果表明，空间裁剪和概率裁剪方法具有非常高的裁剪效率，整个κ-PNN查询处理过程是可靠高效的。
非确定数据库需要研究的问题还很多，在许多查询问题上欠缺高效的处理算法，例如概率连接问题，概率Top-κ查询，概率反最近邻查询，以及概率反轮廓查询等等，因此，针对不同方面的概率空间和时空查询问题，将相应解决方法融入到数据库管理系统中以支持非确定数据的有效管理，将是研究人员面临的新问题。此外，将已有的研究成果应用于多维空间，并进一步考虑非欧式距离环境下的索引及查询处理方法可作为未来的研究方向。在非确定数据流环境下，如何利用有效的内存索引机制，提出各种高效的数据流查询算法也将是非常有潜力的研究课题。
One of the most important research issues in MOD is the problem of modeling andquerying the location of moving objects. Much work exists on traditional spatial andspatio-temporal queries, but there has recently attracted much research interest inevaluating such queries in the presence of uncertainty. This is reasonable, due to locationupdate delay, sampling error, or limitation of measuring equipments, it is rarely possiblefor the database to record the exact positions of moving objects at all times. Theconventional objects indexing methods and query processing techniques assume that thedata are precise, so they cannot be directly applied for uncertain data processing. As aresult, in the context of uncertain database, efficient indexing methods and correspondingquery processing techniques should be developed to guarantee the accuracy of answer andspeed up the query performance.
U-tree is currently the most popular indexing method for the imprecise positions ofstationary objects. It minimizes the amount of qualification probability computation inrange search and it's fully dynamic for the objects can be inserted or deleted in any order.However, it can not deal with the moving objects with uncertainty.
In the mobile environment, a spatio-temporal indexing structure TPU-tree, which is anovel U-tree based indexing technique, can combine the issues of timestamp to predict thefuture location of uncertain evolving data. Along with the data models capturing thespatial-temporal uncertainty and TPU-tree, a modified p-bound based range queryalgorithms (MP_BBRQ), using probabilistic pruning regions and corresponding decisionheuristic rules, can speed up the probabilistic range queries; and a branch and boundalgorithm for constrained probabilistic skyline (B~2CPS), using the best-first searchstrategy of nearest neighbor, can minimum the node access numbers.
New probabilistic spatial queries are more expensive to compute. The disk I/O- andcomputationally-efficient algorithms should be explored to enhance the performance ofprobabilistic range queries, probabilistic k nearest-neighbor queries. Specifically, aprobabilistic k nearest neighbor query returns k objects with the highest probability ofbeing the k-th nearest neighbor to a given query point Q. Comparedto the k-NN query intraditional databases, which retrieves k closest objects to the given query point, thecomputation cost of k-PNN is very expensive due to the costly numerical integration orMonte-Carlo approach it adopts. In order to speed up the k-PNN query processing,efficient spatial and probabilistic pruning approaches are used to reduce the search space,thus the costly numerical evaluation of complex integrals can be avoided as much aspossible. The Spatial and probabilistic pruning approaches can be seamless integrated inthe query procedure. Extensive experiments have been conducted to demonstrate theefficiency and effectiveness of algorithms under various parameter settings.
There are many research issues exist in the uncertain database. It would be interestingto apply new probabilistic queries techniques to solve new problems are explored, such asprobabilistic joins, probabilistic Top-k, probabilistic reverse nearest neighbors, andprobabilistic reverse skyline queries. For these kinds of probabilistic queries, how tointegrate these processing methods to DMBS will be new research issues. Furthermore,extend the current works to handle high dimensional data, and consider non-Euclideandistance could be another interesting directions. In the uncertain streaming environment,how to develop efficient memory indexing method, and speed up kind of streamingqueries will also be very potential research problems.
引文
[1] A. Prasad Sistla, Ouri Wolfson, Sam Chamberlain, et al. Modeling and Querying Moving Objects. In: Proceedings of IEEE Int. Conf. on Data Engineering (ICDE). 1997, 422-432
[2] Ouri Wolfson, Sam Chamberlain, Son Dao, et al. Cost and Imprecision in Modeling the Position of Moving Objects. In: Proceedings of the Fourteenth International Conference on Data Engineering. IEEE Computer Society Press, 1998, 588-596
[3] Ouri Wolfson, Bo Xu, Sam Chamberlain, et al. Moving Objects Databases: Issues and Solutions In: Proceedings. Scientific and Statistical Database Management, 1998, Tenth International Conference on. Capri, Italy. 1998, page(s): 111-122
[4] Ouri Wolfson, A. Prasad Sistla, Sam Chamberlain, et al. Updating and Querying Databases that Track Mobile Units. Distributed and Parallel Databases, 1999, 7(3): 257-387
[5] 王英杰，袁勘省，余卓渊．多维动态地学信息可视化．北京：科学出版社，2003
[6] Congjun Yang, King-Ip Lin. An index strncmre for efficient reverse nearest neighbor queries. In: Proceedings of Data Engineering, ICDE 2001. IEEE 23rd International Conference on. Heidelberg, Germany. 2001, Pages: 485-492
[7] Cui Yu, Beng Chin Ooi, Kian-Lee Tan, et al. Indexing the Distances: An Efficient Method to KNN Processing. In: Proceedings ot the 27th VLDB Conference. Roma, Italy. 2001, 421-430
[8] Yufei Tao, Christos Faloutsos, Dimitris Papadias, et al. Prediction and Indexing of Moving Objects with Unknown Motion Patterns. In: Proceedings of the Int'l Conf. on Management of Data (SIGMOD). Paris, France. 2004, 611-622
[9] Antomn Guttman. R-trees: A Dynamic Index Structure for Spatial Searching. In: Proceedings of the 1984 ACM SIGMOD Internatinal Conference on Management of Data. Boston. 1984, 47-57
[10] 张明波，陆锋，申排伟等．R树家族的演变和发展．计算机学报，2005，28(3)：289-300
[11] Volker Gaede, Oliver Gunther. Multidimensional access methods. ACM Computing Surveys, 1998, 30(2): 170-231
[12] Mohamed F. Mokbel, Thanaa M. Ghanem, Walid G. Aref. Spatio-temporal access methods. IEEE Data Engineering Bulletin, 2003, 26(2): 40-49
[13] Danzhou Liu, Ee-Peng Lim, Wee-Keong Ng. Efficient k Nearest Neighbor Queries on Remote Spatial Databases Using Range Estimation. In: Proceedings of the 14th Internatinal Conference on Scientific and Statistical Database Management (SSDBM'02). 2002, 121-130
[14] King LumCheung, Ada Wai-chee Fu. Enhanced Nearest Neighbor Search on the R-Tree. ACM SIGMOD Record, 1998,27(3): 16-21
[15] Flip Korn, S. Muth ukrishnan. Influence Sets Based on Reverse Nearest Neighbor Queries. In: Proceedings of the 2000 ACM SIGMOD Int'l Conf. on Management of Data. Dallas, Texas, USA. 2000,201-212
[16] Ioana Stanoi, Mirek Riedewald, Divyakant Agrawal, et al. Discovery of Influence Sets in Frequently Updated Databases. In: Proceedings of the 27th VLDB Conference. Roma, Italy. 2001, 99-108
[17] Ioana Stanoi, Divyakant Agrawal, Amr El Abbadi. Reverse Nearest Neighbor queries for Dynamic Databases. In: In Proceedings of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD). Dallas, TX. 2000, 44-53
[18] Anil Maheshwari, Jan Vahrenhold, Norbert Zeh. On Reverse Nearest Neighbor Queries. In: Proceedings of the 14th Canadian Conference on Computational Geometry. 2002, 128-132
[19] Dimitris Papadias, Qiongmao Shen, Yufei Tao, et al. Group Nearest Neighbor Queries. In: Proceedings of the 20th International Conference on Data Engineering. 2004, 301-312
[20] Jun Zhang, Nikos Mamoulis, Dimitris Papadias, et al. All-Nearest-Neighbors Queries in Spatial Databases. In: Proceedings of IEEE Conf. on Scientific and Statistical Database Management (SSDBM). 2004, 297-306
[21] Haibo Hu, Jianliang Xu, Dik Lun Lee. A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects. In: Proceedings of the SIGMOD Int'l Conf. on Management of Data. Baltimore, Maryland, USA. 2005,479-490
[22] Yufei Tao, Dimitris Papadias, Qiongmao Shen. Continuous Nearest Neighbor Search. In: Proceedings of the 28th VLDB Conference. Hong Kong, China. 2002, 287-298
[23] Glenn S. Iwerks, Hanan Samet, Ken Smith. Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates. In: Proceedings of the 28th VLDB Conference. Berlin, Germany. 2003, 512-523
[24] Yifan Li, Jiong Yang, Jiawei Han. Continuous K-Nearest Neighbor Search for Moving Objects. In: Proceedings of Int'l Conference on Scientific and Statistical Database Management (SSDBM). Northwest Washington. 2004, 123-126
[25] Yufei Tao, Dimitris Papadias. Spatial Queries in Dynamic Enviroments. ACM Transactions on Database Systems, 2003, 28(2): 101-139
[26] Jimeng Sun, Dimitris Papadias, Yufei Tao, et al. Querying about the Past, the Present, and the Future in Spatial-Temproal Databases. In: Proceedings of ICDE.Los Alamitos,CA, 2004, 202-213
[27] Yufei Tao, Jun Zhang, Dimitris Papadias, et al. An Efficient Cost Model for Optimization of Nearest Neighbor Search in Low and Medium Dimensional Spaces. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(10):1169-1184
[28] Yufei Tao, Dimitris Gunopulos. Performance Analysis of R*-Trees with Arbitrary Node Extents. IEEE Transactions on Knowledge and Data Engineering, 2004,16(6): 653-668
[29] Yannis Theodoridis, Michael Vazirgiannis, Timos Sellis. Spatio-temporal indexing for large multimedia applications. In: Proceeding of the 3rd IEEE Conference on Multimedia Computing and Systems (ICMCS). 1996, 441-448
[30] Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, et al. Indexing the Positions of Continuously Moving Objects. In: Proceedings of the 2000 SIGMOD International Conf. on Management of Data. Dallas, TX USA. 2000, 331-342
[31] Yufei Tao, Dimitris Papadias. The MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries. In: Proceedings of the 27th VLDB Conference. Roma,Italy. 2001, 431-440
[32] Sunil Prabhakar, Yuni Xia, Dmitri V. Kalashnikov, et al. Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects. IEEE Transactions on Knowledge and Data Engineering, 2002,51(10): 1124-1140
[33] Mohamed F. Mokbel, Xiaopeng Xiong, Walid G. Aref. SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases. In: Proceedings of the ACM SIGMOD International Conference on Management of Data Paris, France. 2004, 623-634
[34] Xiaopeng Xiong, Mohamed F. Mokbel, Walid G. Aref. SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases. In: Proceedings of the 21st International Conference on Data Engineering. 2005, 643-654
[35] Dimitris Papadias, Jun Zhang, Nikos Mamoulis, et al. Query Processing in Spatial Network Databases. In: Proceedings of the 29th VLDB Conference. Berlin,Germany. 2003, 802-813
[36] Ralf Hartmut G(?)ting, Victor Teixeira de Almeida, Zhiming Ding. Modeling and querying moving objects in networks. The VLDB Journal, 2006, 15(2): 165-190
[37] V. Prasad Chakka, Adam C. Everspaugh, Jignesh M. Patel. Indexing Large Trajectory Data Sets with SETI. In: Proceeding of the Conference on Innovative Data Systems Research. Asilomar, CA. 2003, 164-175
[38] Dieter Pfoser, Christian S. Jensen, Yannis Theodoridis. Novel approaches to the indexing of moving object trajectories. In: Proceeding of the 26thVLDB Conference. Cairo, Egypt. 2000, 395-406
[39] Yufei Tao, Dimitris Papadias, Jimeng Sun. The TPR~*-Tree: An Optimized Spatio-temporal Access Method for Predictive Queries. In: Proceedings of the 29 international conference on Very large data bases (VLDB'04). Berlin, Germany. 2003, 790-801
[40] Mong Li Lee, Wynne Hsu, Christian S. Jensen, et al. Supporting Frequent Updates in R-Trees: A Bottom-up Approach. In: Proceedings of the 29th VLDB Conference. Berlin,Germany. 2003, 608-619
[41] Dongseop Kwon, Sangjun Lee, Sukho Lee. Indexing the Current Positions of Moving Objects Using the Lazy Update R-tree. In: 3rd International Conference on Mobile Data Management. 2002, 113-120
[42] Reynold Cheng, Yuni Xia, Sunil Prabhakar, et al. Change Tolerant Indexing for Constantly Evolving Data. In: Proceedings ot the 21st International Conference on Data Engineering 2005, 391 -402
[43] Yuni Xia, Sunil Prabhakar. Q+Rtree: Efficient Indexing for Moving Objects Databases. In: Proceedings of the 8th International Conference on Database System for Advanced Applications (DASFAA). 2003, 175-182
[44] Xiaopeng Xiong, Walid G. Aref. R-Trees with Update Memos. In: Proceedings of the 22nd International Conference on Data Engineering. 2006, 22-31
[45] Hee-Kap Ann, Nikos Mamoulis, Ho Min Wong. A survey on multidimensional access methods. UU-CS, Utrecht. The Netherlands, 2001
[46] Samet Hanan. The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1990
[47] Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM 1975, 18(9): 509-517
[48] Aklil Kumar. G-Tree: A New Data Structure for Organizing Multidimensional Data. IEEE Transactions on Knowledge and Data Engineering 1994, 6(2): Pages:341-347
[49] Bertino E. Indexing Techniques for Advanced Database Systems. Kluwer Academic Publishers, 1998
[50] Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, et al. The R~*-tree:An efficient and robust access method for points and rectangles. In: Proceedings of the 1990 ACM SIGMOD international conference on Management of data. New Jersey. 1990, 322-331
[51] Timos Sellis, Nick Roussopoulos, Christos Faloutsos. the R+-tree: a dynamic index for multi-dimensional objects. In: Proceedings of the 13th International Conference on VLDB. 1987, 507-518
[52] Rimantas Benetis, Christian S. Jensen, Gytis Karciauskas, et al. Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects. In: Proceedings of the Int'l Database Engineering and Applications Symposium. 2002, 44-53
[53] Sangyong Hwang, Keunjoo Kwon, Sang K.Cha, et al. Performance Evaluation of Main-Memory R-tree Variants. Lecture Notes in Computer Science, 2003, 2750(2003): 10-27
[54] Yufei Tao, Nikos Mamoulis, Dimitris Papadias. Validity Information Retrieval for Spatio-temporal Queries: Theoretical Performance Bounds. In: Proceedings of the 8th International Symposium on Spatial and Temporal Databases. 2003, 159-178
[55] Mohamed F.Mokbel, Walid G. Aref. On Query Processing and Optimality Using Spectral Locality-Preserving Mapping. In: Proceedings of the 8th International Symposium on Spatial and Temporal Databases. Santorini Island, Greece. 2003,102-121
[56] Antonio Corral, Yannis Manolopoulos, Yannis Theodoridis, et al. Closest pair queries in spatial databases. In: Proceedings of ACM SIGMOD Conference on Management of data. 2000, 189-200
[57] Gisli R. Hjaltason, Hanan Samet. Incremental Distance Join Algorithms for Spatial Databases. In: Proceedings of ACM SIGMOD Conference on Management of Data. Seattle, WA. 1998, 237-248
[58] Xiaopeng Xiong. Scalable Continuous Query Processing and Moving Object Indexing in Spatio-temporal Databases. In: Proceedings of the EDBT Ph.D.Workshop. Munich, Germany. 2006, 12-21
[59] Hyoseop Shin, Bongki Moon, Sukho Lee. Adaptive and Incremental Processing for Distance Join Queries. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(6): 1561-1578
[60] Kun-Lung Wu, Shyh-Kwei Chen, Philip S. Yu. Incremental Processing of Continual Range Queries over Moving Objects. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(11): 1560-1575
[61] Congjun Yang, King-Ip Lin. An index structure for improving closest pairs and related join queries in spatial databases. In: Proceedings of the International Database Engineering and Applications Symposium (IDEAS' 02). 2002, 140-149
[62] Kyriakos Mouratidis, Dimitris Papadias, Spiridon Bakiras, et al. A Threshold-Based Algorithm for Continuous Monitoring of k Nearest Neighbors.IEEE Transactions on Knowledge and Data Engineering, 2005, 17(11):1451-1464
[63] Nick Roussopoulos, Stephen Kelley, Frederic Vincent. Nearest Neighbor queries. In: Proceedings of ACM SIGMOD International Conference on Management of Data. San Jose, USA. 1995, 71-79
[64] Gisli R. Hjaltason, Hanan Samet. Distance Browsing in Spatial Databases. ACM Transactions on Database Systems, 1999,24(2): 265-318
[65] Apostolos Papadopoulos, Yannis Manolopoulos. Performance of Nearest Neighbor Queries in R-Trees. In: Proceedings of the 6th International Conference on Database Theory. 1997, 394 - 408
[66] Norio Katayama, Shin'ichi Satoh. The SR-tree: An index structure for high-dimensional nearest neighbor queries. In: Proceedings of the 1997 ACM SIGMOD. 1997, 369 - 380
[67] Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, et al. Fast nearest neighbor search in medical image databases. In: In Proceedings of the Int. Conf. on Very Large Data Bases 1996, 215 - 226
[68] Glenn S. Iwerks, Hanan Samet, Kenneth P. Smith. Maintenance of K-nn and Spatial Join Queries on Continuously Moving Points. ACM Transactions on Database Systems, 2006, 31(2): 485-536
[69] Bugra Gedic, Kun-Lung Wu, Philip S. Yu, et al. Processing Moving Queries over Moving Objects Using Motion-Adaptive Indexes. IEEE Transactions on Knowledge and Data Engineering, 2006,18(5): 651 -668
[70] Gerhard Albers, Joseph S. B. Mitchell, Leonidas J. Guibas, et al. Voronoi diagrams of moving points. International Journal of Computational Geometry & Applications, 1998, 8(03): 365 - 380
[71] George Kollios, Dimitrios Gunopulos. Nearest Neighbor Queries in a Mobile Environment. In: Proceedings of the International Workshop on Spatio-Temporal Database Management. Edinburgh, Scotland. 1999,119-129
[72] Zhexuan Song, Nick Roussopoulos. K-Nearest Neighbor Search for Moving Query Point. In: Proceedings of the 7 International Symposium on Spatial and Temporal Databases. Berlin. Springer-Verlag Press, 2001, Pages:79-96
[73] Yufei Tao, Dimitris Papadias. Time-parameterized queries in spatio-temporal database. In: Proceedings of the 2002 ACM SIGMOD Internatinal Conference on Management of Data. 2002, 334-345
[74] Amit Singh, Hakan Ferhatosmanoglu, Ali Saman Tosun. High Dimensional Reverse Nearest Neighbor Queries. In: Proceedings of the twelfth international conference on Information and knowledge management 2003, Pages: 91-98
[75] Yufei Tao, Dimitris Papadias, Xiang Lian. Reverse kNN Search in Arbitrary Dimensionality. In: Proceedings of the Thirtieth international conference on Very large data bases (VLDB'04). 2004, Pages: 744 - 755
[76] Yufei Tao, Dimitris Papadias, Xiang Lian, et al. Multi-dimensional reverse kNN search. VLDB Journal (International Journal on Very Large Data Base), 2007,16(3): Pages: 293-316
[77] Yufei Tao, Man Lung Yiu, N. Mamoulis. Reverse Nearest Neighbor Search in Metric Spaces. IEEE Transactions on Knowledge and Data Engineering, 2006,18(9): Page(s): 1239-1252
[78] Rimantas Benetis, S. Jensen, Gytis Kar(?)iauskas, et al. Nearest and Reverse Nearest Neighbor Queries for Moving Objects. The VLDB Journal — The International Journal on Very Large Data Bases, 2006, 15(3): Pages: 229 - 249
[79] Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger. Efficient Processing of Spatial Joins Using R-trees. In: Proceedings of ACM SIGMOD. Washington DC.1993,237-246
[80] Ming-Ling Lo, Chinya V. Ravishankar. Spatial joins using seeded trees. ACM SIGMOD Record, 1994, 23(2): Pages: 209 - 220
[81] Nikos Mamoulis, Dimitis Papadias. Integration of Spatial Join Algorithms for Processing Multiple Inputs. ACM SIGMOD Record, 1999, 28(2): Pages: 1 -12
[82] Jignesh M. Patel, David J. DeWitt. Partition Based Spatial-merge Join. In: Proceedings of the 1996 ACM SIGMOD international conference on Management of data. 1996
[83] Jimeng Sun, Yufei Tao, Dimitris Papadias, et al. Spatio-Temporal Join Selectivity. Information Systems, 2006, 31(8)
[84] Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, et al. Scalable Sweeping-Based Spatial Join. In: Proceedings of the 24th VLDB Conference. 1998,570-581
[85] Yun-Wu Huang, Ning Jing. Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations. In: Proceedings of the 23rd VLDB Conference.Athens, Greece. 1997, 396-405
[86] Glenn S. Iwerks, Hanan Samet, Kenneth P. Smith. Maintenance of Spatial Semijoin Queries on Moving Points. In: Proceedings of the 30th VLDB Conference. Toronto, Canada. 2004, 828-839
[87] Antonio Corral, Yannis Manolopoulos, Yannis Theodoridis, et al. Algorithms for processing K-closest-pair queries in spatial databases. IEEE Transactions on Knowledge and Data Engineering, 2004, 49(1): 67-104
[88] Antonio Corral, Michael Vassilakopoulos, Yannis Manolopoulos. The Impact of Buffering on Closest Pairs Queries Using R-Trees. In: Proceedings of the 5th East European Conference on Advances in Databases and Information Systems. 2001,41-51
[89] Manli Zhu, Dimitris Papadias, Jun Zhang, et al. Top-k Spatial Joins. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(4): 567-579
[90] Jing Shan, Donghui Zhang, Betty Salzberg. On Spatial-Range Closest-Pair Query.In: Proceedings of 8th Symposium on Spatial and Temporal Databases (SSTD'03).2003,252-269
[91] Fabrizio Angiulli, Clara Pizzuti. Top-k Closest Pairs Join Query: An Approximate Algorithm for Large High Dimensional Data. In: Proceedings of the International Database Engineering and Applications Symposium (IDEAS'04). 2004, 103-110
[92] Manli Zhu, Dik Lun Lee, Jun Zhang. k-Closest Pair Query Monitoring Over Moving Objects. In: Proceedings of the 7th International Conference on Mobile Data Management (MDM'06). 2006, 14-21
[93] Hyoseop Shin, Bongki Moon, Sukho Lee. Tie-breaking strategies for fast distance join processing. IEEE Transactions on Knowledge and Data Engineering, 2002,41(1): 67-83
[94] Christos Faloutsos, Bernhard Seeger, Agma Traina, et al. Spatial Join Selectivity Using Power laws. In: Proceedings of 2000 ACM-SIGMOD Internatinal Conference on Management of Data. 2000, 177-188
[95] Hyoseop Shin, Bongki Moon, Sukho Lee. Adaptive Multi-stage Distance Join Processing. In: Proceedings of ACM SIGMOD Conference. Dallas, TX, USA. 2000,343-354
[96] 陈军. Voronoi 动态空间数据模型.北京:测绘出版社, 2002
[97] A. Prasad Sistla, Ouri Wolfson, Sam Chamberlain, et al. Querying the uncertain position of moving objects. In: Temporal Databases: Research and Practice.LNCS Press, 1998, 310-337
[98] Dieter Pfoser, Christian S. Jensen. Capturing the Uncertainty of Moving-Object Representations. In: Proceedings of the 11th Internatinal Conference on Scientific and Statistical Database Management (SSDBM'1999). 1999, Pages: 123 -132
[99] T. Abdessalem, J. Moreira, C. Ribeiro. Movement query operations for spatio-temporel databases. In: Proc. 17(?)mes Journ(?)es Bases de Donn(?)es Avancees (BDA'01). Agadir, Maroc. 2001
[100] Jennifer Widom. Trio: A system for integrated management of data, accuracy, and lineage. In: Proc. of the 2nd Biennial Conf. on Innovative Data Systems Research (CIDR). 2005
[101] Reynold Cheng, Yuni Xia, Sunil Prabhakar, et al. Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data. In: Very Large Databases Conference (VLDB 2004), Toronto, Canada, Sep 2004. pp. 876-887
[102] Reynold Cheng, Sarvjeet Singh, Sunil Prabhakar. U-DBMS: A Database System for Managing Constantly-Evolving Data. In: Very Large Databases Conf. (VLDB 2005 Demo), Trondheim, Norway. Aug 2005
[103] Sarvjeet Singh, Chris Mayfield, Sagar Mittal, et al. Orion 2.0: Native Support for Uncertain Data. In: Proc. of the ACM Special Interest Group on Management of Data (SIGMOD 2008), Vancouver, Canada, June 2008
[104] Reynold Cheng, Dmitri V. Kalashnikov, Sunil Prabhakar. Querying Imprecise Data in Moving Object Environments. IEEE Transactions on Knowledge and Data Engineering (IEEE TKDE), Vol. 16, No. 9, Sep 2004: pp. 1112-1127
[105] Reynold Cheng, Dmitri V. Kalashnikov, Sunil Prabhakar. Evaluating Probabilistic Queries over Imprecise Data. In: Proc. of the ACM Special Interest Group on Management of Data (ACM SIGMOD 2003), pp. 551-562, June 2003
[106] Yufei Tao, Reynold Cheng, Xiaokui Xiao, et al. Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions. In: Proceedings of the 31 st VLDB Conference. Trondheim, Norway. 2005
[107] Nilesh Dalvi, Dan Suciu. Efficient Query Evaluation on Probabilistic Databases. In: Proceedings of the Thirtieth international conference on Very large data bases (VLDB'04). 2004, Pages: 864 - 875
[108] Nilesh Dalvi, Dan Suciu. Management of Probabilistic Data: Foundations and Challenges. In: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (PODS'07). Beijing, China. 2007, Pages: 1 - 12
[109] Dan Lin, Christian S. Jensen, Beng Chin Ooi, et al. Efficient indexing of the historical, present, and future positions of moving objects. In: Proceedings of the 6th international conference on Mobile data management Ayia Napa, Cyprus 2005,Pages: 59-66
[110] Mindaugas Pelanis, Simonas Saltenis, Christian S. Jensen. Indexing the Past, Present and Anticipated Future Positions of Moving Objects. ACM Trans, on Database Systems (TODS), 2006,31(1):255-298
[111] Xiaofeng Ding, Yansheng Lu. Indexing the Imprecise Positions of Moving Objects. In: Proc. ACM SIGMOD 2007 Ph.D. Workshop on Innovative Database Research. Beijing, China. 2007, 45 - 50
[112] Xiaopeng Xiong, Mohamed F. Mokbel, Walid G. Aref. LUGrid: Update-tolerant Grid-based Indexing for Moving Objects. In: Proceedings of the IEEE International Conference of Mobile Data Management (MDM). Nara, Tokyo. 2006, 13-26
[113] Christos Faloutsos, Timos Sellis, Nick Roussopoulos. Analysis of object oriented spatial access methods. In: Proceedings of the 1987 ACM SIGMOD international conference on Management of Data. 1987, 426-439
[114] Yun-Wu Huang, Ning Jing. A Cost Model for Estimating the Performance of Spatial Joins Using R-Trees. In: Proceedings of 9th International Conference on Scientific and Statistical Database Management 1997, 30-38
[115] Thomas Brinkhoff. A Framework for Generating Network-Based Moving Objects. Geoinformatica, 2002, 6(2): 153 - 180
[116] Dimitris Papadias, Yufei Tao, G. Fu, et al. An optimal and progressive algorithm for skyline queries. In: Proceedings of the 2003 ACM SIGMOD international conference on Management of data. 2003, pages: 467-478
[117] Ravi Jampani, Fei Xu, Mingxi Wu, et al. MCDB: a monte carlo approach to managing uncertain data. In: Proceedings of the 2008 ACM SIGMOD international conference on Management of data. Vancouver, Canada. 2008, Pages 687-700
[118] Xiang Lian, Lei Chen. Probabilistic Ranked Queries in Uncertain Databases. In:Proceedings of the 11th international conference on Extending database technology: Advances in database technology Nantes, France. 2008, Pages 511-522
[119] Christopher Re, Nilesh Dalvi, Dan Suciu. Efficient top-k query evaluation on probabilistic data. In: Proceeding Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on. page(s): 886-895
[120] Jian Pei, Bin Jiang, Xuemin Lin, et al. Probabilistic skylines on uncertain data. In: Proceedings of the 33rd international conference on Very large data bases (VLDB'07). Vienna, Austria. 2007, Pages 15-26
[121] Xiang Lian, Lei Chen. Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Database. In: Proceedings of the 2008 ACM SIGMOD international conference on Management of data. Vancouver, Canada. 2008, Pages 213-226
[122] Xiaohui Yu, Ken Q. Pu, Nick Koudas. Monitoring k-Nearest Neighbor Queries Over Moving Objects. In: Proceedings of Data Engineering, 2005. ICDE 2005.IEEE 23rd International Conference on. Tokyo, Japan. Pages: 631-642
[123] Kyriakos Mouratidis, Marios Hadjieleftheriou, Dimitris Papadias. Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring.In: Proceedings of the SIGMOD Int'l Conf. on Management of Data. 2005,634-645
[124] Reynold Cheng, Jinchuan Chen, Mohamed F. Mokbel, et al. Probabilistic Verifiers: Evaluating Constrained Nearest-Neighbor Queries over Uncertain Data. In:Proceeding Data Engineering. ICDE 2008. IEEE 24th International Conference on. 2008, 973-982
[125] Hans-Peter Kriegel, Peter Kunath, Matthias Renz. Probabilistic Nearest-Neighbor Query on Uncertain Objects In: Proc. 12th Int'l Conf. Database Systems for Advanced Applications (DASFAA'07). 2007
[126] Vebjorn Ljosa, Ambuj K. Singh. APLA: Indexing Arbitrary Probability Distributions. In: Proceeding of Data Engineering. ICDE 2007. IEEE 23rd International Conference on. 2007, page(s): 946-955
[127] George Beskales, Mohamed A. Soliman, Ihab F. Ilyas. Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases. In: Proceedings of the 34th International Conference on Very Large Data Bases, VLDB 2008, Auckland,New Zealand. 2008, pp. 326-339
[128] http://www.census.gov/geo/www/tiger/
[2] Ouri Wolfson, Sam Chamberlain, Son Dao, et al. Cost and Imprecision in Modeling the Position of Moving Objects. In: Proceedings of the Fourteenth International Conference on Data Engineering. IEEE Computer Society Press, 1998, 588-596
[3] Ouri Wolfson, Bo Xu, Sam Chamberlain, et al. Moving Objects Databases: Issues and Solutions In: Proceedings. Scientific and Statistical Database Management, 1998, Tenth International Conference on. Capri, Italy. 1998, page(s): 111-122
[4] Ouri Wolfson, A. Prasad Sistla, Sam Chamberlain, et al. Updating and Querying Databases that Track Mobile Units. Distributed and Parallel Databases, 1999, 7(3): 257-387
[5] 王英杰，袁勘省，余卓渊．多维动态地学信息可视化．北京：科学出版社，2003
[6] Congjun Yang, King-Ip Lin. An index strncmre for efficient reverse nearest neighbor queries. In: Proceedings of Data Engineering, ICDE 2001. IEEE 23rd International Conference on. Heidelberg, Germany. 2001, Pages: 485-492
[7] Cui Yu, Beng Chin Ooi, Kian-Lee Tan, et al. Indexing the Distances: An Efficient Method to KNN Processing. In: Proceedings ot the 27th VLDB Conference. Roma, Italy. 2001, 421-430
[8] Yufei Tao, Christos Faloutsos, Dimitris Papadias, et al. Prediction and Indexing of Moving Objects with Unknown Motion Patterns. In: Proceedings of the Int'l Conf. on Management of Data (SIGMOD). Paris, France. 2004, 611-622
[9] Antomn Guttman. R-trees: A Dynamic Index Structure for Spatial Searching. In: Proceedings of the 1984 ACM SIGMOD Internatinal Conference on Management of Data. Boston. 1984, 47-57
[10] 张明波，陆锋，申排伟等．R树家族的演变和发展．计算机学报，2005，28(3)：289-300
[11] Volker Gaede, Oliver Gunther. Multidimensional access methods. ACM Computing Surveys, 1998, 30(2): 170-231
[12] Mohamed F. Mokbel, Thanaa M. Ghanem, Walid G. Aref. Spatio-temporal access methods. IEEE Data Engineering Bulletin, 2003, 26(2): 40-49
[13] Danzhou Liu, Ee-Peng Lim, Wee-Keong Ng. Efficient k Nearest Neighbor Queries on Remote Spatial Databases Using Range Estimation. In: Proceedings of the 14th Internatinal Conference on Scientific and Statistical Database Management (SSDBM'02). 2002, 121-130
[14] King LumCheung, Ada Wai-chee Fu. Enhanced Nearest Neighbor Search on the R-Tree. ACM SIGMOD Record, 1998,27(3): 16-21
[15] Flip Korn, S. Muth ukrishnan. Influence Sets Based on Reverse Nearest Neighbor Queries. In: Proceedings of the 2000 ACM SIGMOD Int'l Conf. on Management of Data. Dallas, Texas, USA. 2000,201-212
[16] Ioana Stanoi, Mirek Riedewald, Divyakant Agrawal, et al. Discovery of Influence Sets in Frequently Updated Databases. In: Proceedings of the 27th VLDB Conference. Roma, Italy. 2001, 99-108
[17] Ioana Stanoi, Divyakant Agrawal, Amr El Abbadi. Reverse Nearest Neighbor queries for Dynamic Databases. In: In Proceedings of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD). Dallas, TX. 2000, 44-53
[18] Anil Maheshwari, Jan Vahrenhold, Norbert Zeh. On Reverse Nearest Neighbor Queries. In: Proceedings of the 14th Canadian Conference on Computational Geometry. 2002, 128-132
[19] Dimitris Papadias, Qiongmao Shen, Yufei Tao, et al. Group Nearest Neighbor Queries. In: Proceedings of the 20th International Conference on Data Engineering. 2004, 301-312
[20] Jun Zhang, Nikos Mamoulis, Dimitris Papadias, et al. All-Nearest-Neighbors Queries in Spatial Databases. In: Proceedings of IEEE Conf. on Scientific and Statistical Database Management (SSDBM). 2004, 297-306
[21] Haibo Hu, Jianliang Xu, Dik Lun Lee. A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects. In: Proceedings of the SIGMOD Int'l Conf. on Management of Data. Baltimore, Maryland, USA. 2005,479-490
[22] Yufei Tao, Dimitris Papadias, Qiongmao Shen. Continuous Nearest Neighbor Search. In: Proceedings of the 28th VLDB Conference. Hong Kong, China. 2002, 287-298
[23] Glenn S. Iwerks, Hanan Samet, Ken Smith. Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates. In: Proceedings of the 28th VLDB Conference. Berlin, Germany. 2003, 512-523
[24] Yifan Li, Jiong Yang, Jiawei Han. Continuous K-Nearest Neighbor Search for Moving Objects. In: Proceedings of Int'l Conference on Scientific and Statistical Database Management (SSDBM). Northwest Washington. 2004, 123-126
[25] Yufei Tao, Dimitris Papadias. Spatial Queries in Dynamic Enviroments. ACM Transactions on Database Systems, 2003, 28(2): 101-139
[26] Jimeng Sun, Dimitris Papadias, Yufei Tao, et al. Querying about the Past, the Present, and the Future in Spatial-Temproal Databases. In: Proceedings of ICDE.Los Alamitos,CA, 2004, 202-213
[27] Yufei Tao, Jun Zhang, Dimitris Papadias, et al. An Efficient Cost Model for Optimization of Nearest Neighbor Search in Low and Medium Dimensional Spaces. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(10):1169-1184
[28] Yufei Tao, Dimitris Gunopulos. Performance Analysis of R*-Trees with Arbitrary Node Extents. IEEE Transactions on Knowledge and Data Engineering, 2004,16(6): 653-668
[29] Yannis Theodoridis, Michael Vazirgiannis, Timos Sellis. Spatio-temporal indexing for large multimedia applications. In: Proceeding of the 3rd IEEE Conference on Multimedia Computing and Systems (ICMCS). 1996, 441-448
[30] Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, et al. Indexing the Positions of Continuously Moving Objects. In: Proceedings of the 2000 SIGMOD International Conf. on Management of Data. Dallas, TX USA. 2000, 331-342
[31] Yufei Tao, Dimitris Papadias. The MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries. In: Proceedings of the 27th VLDB Conference. Roma,Italy. 2001, 431-440
[32] Sunil Prabhakar, Yuni Xia, Dmitri V. Kalashnikov, et al. Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects. IEEE Transactions on Knowledge and Data Engineering, 2002,51(10): 1124-1140
[33] Mohamed F. Mokbel, Xiaopeng Xiong, Walid G. Aref. SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases. In: Proceedings of the ACM SIGMOD International Conference on Management of Data Paris, France. 2004, 623-634
[34] Xiaopeng Xiong, Mohamed F. Mokbel, Walid G. Aref. SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases. In: Proceedings of the 21st International Conference on Data Engineering. 2005, 643-654
[35] Dimitris Papadias, Jun Zhang, Nikos Mamoulis, et al. Query Processing in Spatial Network Databases. In: Proceedings of the 29th VLDB Conference. Berlin,Germany. 2003, 802-813
[36] Ralf Hartmut G(?)ting, Victor Teixeira de Almeida, Zhiming Ding. Modeling and querying moving objects in networks. The VLDB Journal, 2006, 15(2): 165-190
[37] V. Prasad Chakka, Adam C. Everspaugh, Jignesh M. Patel. Indexing Large Trajectory Data Sets with SETI. In: Proceeding of the Conference on Innovative Data Systems Research. Asilomar, CA. 2003, 164-175
[38] Dieter Pfoser, Christian S. Jensen, Yannis Theodoridis. Novel approaches to the indexing of moving object trajectories. In: Proceeding of the 26thVLDB Conference. Cairo, Egypt. 2000, 395-406
[39] Yufei Tao, Dimitris Papadias, Jimeng Sun. The TPR~*-Tree: An Optimized Spatio-temporal Access Method for Predictive Queries. In: Proceedings of the 29 international conference on Very large data bases (VLDB'04). Berlin, Germany. 2003, 790-801
[40] Mong Li Lee, Wynne Hsu, Christian S. Jensen, et al. Supporting Frequent Updates in R-Trees: A Bottom-up Approach. In: Proceedings of the 29th VLDB Conference. Berlin,Germany. 2003, 608-619
[41] Dongseop Kwon, Sangjun Lee, Sukho Lee. Indexing the Current Positions of Moving Objects Using the Lazy Update R-tree. In: 3rd International Conference on Mobile Data Management. 2002, 113-120
[42] Reynold Cheng, Yuni Xia, Sunil Prabhakar, et al. Change Tolerant Indexing for Constantly Evolving Data. In: Proceedings ot the 21st International Conference on Data Engineering 2005, 391 -402
[43] Yuni Xia, Sunil Prabhakar. Q+Rtree: Efficient Indexing for Moving Objects Databases. In: Proceedings of the 8th International Conference on Database System for Advanced Applications (DASFAA). 2003, 175-182
[44] Xiaopeng Xiong, Walid G. Aref. R-Trees with Update Memos. In: Proceedings of the 22nd International Conference on Data Engineering. 2006, 22-31
[45] Hee-Kap Ann, Nikos Mamoulis, Ho Min Wong. A survey on multidimensional access methods. UU-CS, Utrecht. The Netherlands, 2001
[46] Samet Hanan. The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1990
[47] Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM 1975, 18(9): 509-517
[48] Aklil Kumar. G-Tree: A New Data Structure for Organizing Multidimensional Data. IEEE Transactions on Knowledge and Data Engineering 1994, 6(2): Pages:341-347
[49] Bertino E. Indexing Techniques for Advanced Database Systems. Kluwer Academic Publishers, 1998
[50] Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, et al. The R~*-tree:An efficient and robust access method for points and rectangles. In: Proceedings of the 1990 ACM SIGMOD international conference on Management of data. New Jersey. 1990, 322-331
[51] Timos Sellis, Nick Roussopoulos, Christos Faloutsos. the R+-tree: a dynamic index for multi-dimensional objects. In: Proceedings of the 13th International Conference on VLDB. 1987, 507-518
[52] Rimantas Benetis, Christian S. Jensen, Gytis Karciauskas, et al. Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects. In: Proceedings of the Int'l Database Engineering and Applications Symposium. 2002, 44-53
[53] Sangyong Hwang, Keunjoo Kwon, Sang K.Cha, et al. Performance Evaluation of Main-Memory R-tree Variants. Lecture Notes in Computer Science, 2003, 2750(2003): 10-27
[54] Yufei Tao, Nikos Mamoulis, Dimitris Papadias. Validity Information Retrieval for Spatio-temporal Queries: Theoretical Performance Bounds. In: Proceedings of the 8th International Symposium on Spatial and Temporal Databases. 2003, 159-178
[55] Mohamed F.Mokbel, Walid G. Aref. On Query Processing and Optimality Using Spectral Locality-Preserving Mapping. In: Proceedings of the 8th International Symposium on Spatial and Temporal Databases. Santorini Island, Greece. 2003,102-121
[56] Antonio Corral, Yannis Manolopoulos, Yannis Theodoridis, et al. Closest pair queries in spatial databases. In: Proceedings of ACM SIGMOD Conference on Management of data. 2000, 189-200
[57] Gisli R. Hjaltason, Hanan Samet. Incremental Distance Join Algorithms for Spatial Databases. In: Proceedings of ACM SIGMOD Conference on Management of Data. Seattle, WA. 1998, 237-248
[58] Xiaopeng Xiong. Scalable Continuous Query Processing and Moving Object Indexing in Spatio-temporal Databases. In: Proceedings of the EDBT Ph.D.Workshop. Munich, Germany. 2006, 12-21
[59] Hyoseop Shin, Bongki Moon, Sukho Lee. Adaptive and Incremental Processing for Distance Join Queries. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(6): 1561-1578
[60] Kun-Lung Wu, Shyh-Kwei Chen, Philip S. Yu. Incremental Processing of Continual Range Queries over Moving Objects. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(11): 1560-1575
[61] Congjun Yang, King-Ip Lin. An index structure for improving closest pairs and related join queries in spatial databases. In: Proceedings of the International Database Engineering and Applications Symposium (IDEAS' 02). 2002, 140-149
[62] Kyriakos Mouratidis, Dimitris Papadias, Spiridon Bakiras, et al. A Threshold-Based Algorithm for Continuous Monitoring of k Nearest Neighbors.IEEE Transactions on Knowledge and Data Engineering, 2005, 17(11):1451-1464
[63] Nick Roussopoulos, Stephen Kelley, Frederic Vincent. Nearest Neighbor queries. In: Proceedings of ACM SIGMOD International Conference on Management of Data. San Jose, USA. 1995, 71-79
[64] Gisli R. Hjaltason, Hanan Samet. Distance Browsing in Spatial Databases. ACM Transactions on Database Systems, 1999,24(2): 265-318
[65] Apostolos Papadopoulos, Yannis Manolopoulos. Performance of Nearest Neighbor Queries in R-Trees. In: Proceedings of the 6th International Conference on Database Theory. 1997, 394 - 408
[66] Norio Katayama, Shin'ichi Satoh. The SR-tree: An index structure for high-dimensional nearest neighbor queries. In: Proceedings of the 1997 ACM SIGMOD. 1997, 369 - 380
[67] Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, et al. Fast nearest neighbor search in medical image databases. In: In Proceedings of the Int. Conf. on Very Large Data Bases 1996, 215 - 226
[68] Glenn S. Iwerks, Hanan Samet, Kenneth P. Smith. Maintenance of K-nn and Spatial Join Queries on Continuously Moving Points. ACM Transactions on Database Systems, 2006, 31(2): 485-536
[69] Bugra Gedic, Kun-Lung Wu, Philip S. Yu, et al. Processing Moving Queries over Moving Objects Using Motion-Adaptive Indexes. IEEE Transactions on Knowledge and Data Engineering, 2006,18(5): 651 -668
[70] Gerhard Albers, Joseph S. B. Mitchell, Leonidas J. Guibas, et al. Voronoi diagrams of moving points. International Journal of Computational Geometry & Applications, 1998, 8(03): 365 - 380
[71] George Kollios, Dimitrios Gunopulos. Nearest Neighbor Queries in a Mobile Environment. In: Proceedings of the International Workshop on Spatio-Temporal Database Management. Edinburgh, Scotland. 1999,119-129
[72] Zhexuan Song, Nick Roussopoulos. K-Nearest Neighbor Search for Moving Query Point. In: Proceedings of the 7 International Symposium on Spatial and Temporal Databases. Berlin. Springer-Verlag Press, 2001, Pages:79-96
[73] Yufei Tao, Dimitris Papadias. Time-parameterized queries in spatio-temporal database. In: Proceedings of the 2002 ACM SIGMOD Internatinal Conference on Management of Data. 2002, 334-345
[74] Amit Singh, Hakan Ferhatosmanoglu, Ali Saman Tosun. High Dimensional Reverse Nearest Neighbor Queries. In: Proceedings of the twelfth international conference on Information and knowledge management 2003, Pages: 91-98
[75] Yufei Tao, Dimitris Papadias, Xiang Lian. Reverse kNN Search in Arbitrary Dimensionality. In: Proceedings of the Thirtieth international conference on Very large data bases (VLDB'04). 2004, Pages: 744 - 755
[76] Yufei Tao, Dimitris Papadias, Xiang Lian, et al. Multi-dimensional reverse kNN search. VLDB Journal (International Journal on Very Large Data Base), 2007,16(3): Pages: 293-316
[77] Yufei Tao, Man Lung Yiu, N. Mamoulis. Reverse Nearest Neighbor Search in Metric Spaces. IEEE Transactions on Knowledge and Data Engineering, 2006,18(9): Page(s): 1239-1252
[78] Rimantas Benetis, S. Jensen, Gytis Kar(?)iauskas, et al. Nearest and Reverse Nearest Neighbor Queries for Moving Objects. The VLDB Journal — The International Journal on Very Large Data Bases, 2006, 15(3): Pages: 229 - 249
[79] Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger. Efficient Processing of Spatial Joins Using R-trees. In: Proceedings of ACM SIGMOD. Washington DC.1993,237-246
[80] Ming-Ling Lo, Chinya V. Ravishankar. Spatial joins using seeded trees. ACM SIGMOD Record, 1994, 23(2): Pages: 209 - 220
[81] Nikos Mamoulis, Dimitis Papadias. Integration of Spatial Join Algorithms for Processing Multiple Inputs. ACM SIGMOD Record, 1999, 28(2): Pages: 1 -12
[82] Jignesh M. Patel, David J. DeWitt. Partition Based Spatial-merge Join. In: Proceedings of the 1996 ACM SIGMOD international conference on Management of data. 1996
[83] Jimeng Sun, Yufei Tao, Dimitris Papadias, et al. Spatio-Temporal Join Selectivity. Information Systems, 2006, 31(8)
[84] Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, et al. Scalable Sweeping-Based Spatial Join. In: Proceedings of the 24th VLDB Conference. 1998,570-581
[85] Yun-Wu Huang, Ning Jing. Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations. In: Proceedings of the 23rd VLDB Conference.Athens, Greece. 1997, 396-405
[86] Glenn S. Iwerks, Hanan Samet, Kenneth P. Smith. Maintenance of Spatial Semijoin Queries on Moving Points. In: Proceedings of the 30th VLDB Conference. Toronto, Canada. 2004, 828-839
[87] Antonio Corral, Yannis Manolopoulos, Yannis Theodoridis, et al. Algorithms for processing K-closest-pair queries in spatial databases. IEEE Transactions on Knowledge and Data Engineering, 2004, 49(1): 67-104
[88] Antonio Corral, Michael Vassilakopoulos, Yannis Manolopoulos. The Impact of Buffering on Closest Pairs Queries Using R-Trees. In: Proceedings of the 5th East European Conference on Advances in Databases and Information Systems. 2001,41-51
[89] Manli Zhu, Dimitris Papadias, Jun Zhang, et al. Top-k Spatial Joins. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(4): 567-579
[90] Jing Shan, Donghui Zhang, Betty Salzberg. On Spatial-Range Closest-Pair Query.In: Proceedings of 8th Symposium on Spatial and Temporal Databases (SSTD'03).2003,252-269
[91] Fabrizio Angiulli, Clara Pizzuti. Top-k Closest Pairs Join Query: An Approximate Algorithm for Large High Dimensional Data. In: Proceedings of the International Database Engineering and Applications Symposium (IDEAS'04). 2004, 103-110
[92] Manli Zhu, Dik Lun Lee, Jun Zhang. k-Closest Pair Query Monitoring Over Moving Objects. In: Proceedings of the 7th International Conference on Mobile Data Management (MDM'06). 2006, 14-21
[93] Hyoseop Shin, Bongki Moon, Sukho Lee. Tie-breaking strategies for fast distance join processing. IEEE Transactions on Knowledge and Data Engineering, 2002,41(1): 67-83
[94] Christos Faloutsos, Bernhard Seeger, Agma Traina, et al. Spatial Join Selectivity Using Power laws. In: Proceedings of 2000 ACM-SIGMOD Internatinal Conference on Management of Data. 2000, 177-188
[95] Hyoseop Shin, Bongki Moon, Sukho Lee. Adaptive Multi-stage Distance Join Processing. In: Proceedings of ACM SIGMOD Conference. Dallas, TX, USA. 2000,343-354
[96] 陈军. Voronoi 动态空间数据模型.北京:测绘出版社, 2002
[97] A. Prasad Sistla, Ouri Wolfson, Sam Chamberlain, et al. Querying the uncertain position of moving objects. In: Temporal Databases: Research and Practice.LNCS Press, 1998, 310-337
[98] Dieter Pfoser, Christian S. Jensen. Capturing the Uncertainty of Moving-Object Representations. In: Proceedings of the 11th Internatinal Conference on Scientific and Statistical Database Management (SSDBM'1999). 1999, Pages: 123 -132
[99] T. Abdessalem, J. Moreira, C. Ribeiro. Movement query operations for spatio-temporel databases. In: Proc. 17(?)mes Journ(?)es Bases de Donn(?)es Avancees (BDA'01). Agadir, Maroc. 2001
[100] Jennifer Widom. Trio: A system for integrated management of data, accuracy, and lineage. In: Proc. of the 2nd Biennial Conf. on Innovative Data Systems Research (CIDR). 2005
[101] Reynold Cheng, Yuni Xia, Sunil Prabhakar, et al. Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data. In: Very Large Databases Conference (VLDB 2004), Toronto, Canada, Sep 2004. pp. 876-887
[102] Reynold Cheng, Sarvjeet Singh, Sunil Prabhakar. U-DBMS: A Database System for Managing Constantly-Evolving Data. In: Very Large Databases Conf. (VLDB 2005 Demo), Trondheim, Norway. Aug 2005
[103] Sarvjeet Singh, Chris Mayfield, Sagar Mittal, et al. Orion 2.0: Native Support for Uncertain Data. In: Proc. of the ACM Special Interest Group on Management of Data (SIGMOD 2008), Vancouver, Canada, June 2008
[104] Reynold Cheng, Dmitri V. Kalashnikov, Sunil Prabhakar. Querying Imprecise Data in Moving Object Environments. IEEE Transactions on Knowledge and Data Engineering (IEEE TKDE), Vol. 16, No. 9, Sep 2004: pp. 1112-1127
[105] Reynold Cheng, Dmitri V. Kalashnikov, Sunil Prabhakar. Evaluating Probabilistic Queries over Imprecise Data. In: Proc. of the ACM Special Interest Group on Management of Data (ACM SIGMOD 2003), pp. 551-562, June 2003
[106] Yufei Tao, Reynold Cheng, Xiaokui Xiao, et al. Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions. In: Proceedings of the 31 st VLDB Conference. Trondheim, Norway. 2005
[107] Nilesh Dalvi, Dan Suciu. Efficient Query Evaluation on Probabilistic Databases. In: Proceedings of the Thirtieth international conference on Very large data bases (VLDB'04). 2004, Pages: 864 - 875
[108] Nilesh Dalvi, Dan Suciu. Management of Probabilistic Data: Foundations and Challenges. In: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (PODS'07). Beijing, China. 2007, Pages: 1 - 12
[109] Dan Lin, Christian S. Jensen, Beng Chin Ooi, et al. Efficient indexing of the historical, present, and future positions of moving objects. In: Proceedings of the 6th international conference on Mobile data management Ayia Napa, Cyprus 2005,Pages: 59-66
[110] Mindaugas Pelanis, Simonas Saltenis, Christian S. Jensen. Indexing the Past, Present and Anticipated Future Positions of Moving Objects. ACM Trans, on Database Systems (TODS), 2006,31(1):255-298
[111] Xiaofeng Ding, Yansheng Lu. Indexing the Imprecise Positions of Moving Objects. In: Proc. ACM SIGMOD 2007 Ph.D. Workshop on Innovative Database Research. Beijing, China. 2007, 45 - 50
[112] Xiaopeng Xiong, Mohamed F. Mokbel, Walid G. Aref. LUGrid: Update-tolerant Grid-based Indexing for Moving Objects. In: Proceedings of the IEEE International Conference of Mobile Data Management (MDM). Nara, Tokyo. 2006, 13-26
[113] Christos Faloutsos, Timos Sellis, Nick Roussopoulos. Analysis of object oriented spatial access methods. In: Proceedings of the 1987 ACM SIGMOD international conference on Management of Data. 1987, 426-439
[114] Yun-Wu Huang, Ning Jing. A Cost Model for Estimating the Performance of Spatial Joins Using R-Trees. In: Proceedings of 9th International Conference on Scientific and Statistical Database Management 1997, 30-38
[115] Thomas Brinkhoff. A Framework for Generating Network-Based Moving Objects. Geoinformatica, 2002, 6(2): 153 - 180
[116] Dimitris Papadias, Yufei Tao, G. Fu, et al. An optimal and progressive algorithm for skyline queries. In: Proceedings of the 2003 ACM SIGMOD international conference on Management of data. 2003, pages: 467-478
[117] Ravi Jampani, Fei Xu, Mingxi Wu, et al. MCDB: a monte carlo approach to managing uncertain data. In: Proceedings of the 2008 ACM SIGMOD international conference on Management of data. Vancouver, Canada. 2008, Pages 687-700
[118] Xiang Lian, Lei Chen. Probabilistic Ranked Queries in Uncertain Databases. In:Proceedings of the 11th international conference on Extending database technology: Advances in database technology Nantes, France. 2008, Pages 511-522
[119] Christopher Re, Nilesh Dalvi, Dan Suciu. Efficient top-k query evaluation on probabilistic data. In: Proceeding Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on. page(s): 886-895
[120] Jian Pei, Bin Jiang, Xuemin Lin, et al. Probabilistic skylines on uncertain data. In: Proceedings of the 33rd international conference on Very large data bases (VLDB'07). Vienna, Austria. 2007, Pages 15-26
[121] Xiang Lian, Lei Chen. Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Database. In: Proceedings of the 2008 ACM SIGMOD international conference on Management of data. Vancouver, Canada. 2008, Pages 213-226
[122] Xiaohui Yu, Ken Q. Pu, Nick Koudas. Monitoring k-Nearest Neighbor Queries Over Moving Objects. In: Proceedings of Data Engineering, 2005. ICDE 2005.IEEE 23rd International Conference on. Tokyo, Japan. Pages: 631-642
[123] Kyriakos Mouratidis, Marios Hadjieleftheriou, Dimitris Papadias. Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring.In: Proceedings of the SIGMOD Int'l Conf. on Management of Data. 2005,634-645
[124] Reynold Cheng, Jinchuan Chen, Mohamed F. Mokbel, et al. Probabilistic Verifiers: Evaluating Constrained Nearest-Neighbor Queries over Uncertain Data. In:Proceeding Data Engineering. ICDE 2008. IEEE 24th International Conference on. 2008, 973-982
[125] Hans-Peter Kriegel, Peter Kunath, Matthias Renz. Probabilistic Nearest-Neighbor Query on Uncertain Objects In: Proc. 12th Int'l Conf. Database Systems for Advanced Applications (DASFAA'07). 2007
[126] Vebjorn Ljosa, Ambuj K. Singh. APLA: Indexing Arbitrary Probability Distributions. In: Proceeding of Data Engineering. ICDE 2007. IEEE 23rd International Conference on. 2007, page(s): 946-955
[127] George Beskales, Mohamed A. Soliman, Ihab F. Ilyas. Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases. In: Proceedings of the 34th International Conference on Very Large Data Bases, VLDB 2008, Auckland,New Zealand. 2008, pp. 326-339
[128] http://www.census.gov/geo/www/tiger/