面向位置服务的移动对象索引与查询处理技术研究
|
摘要
位置服务是通过移动终端和无线网络的配合,确定出移动用户的实际地理位置,从而提供用户需要的与位置相关的信息服务。位置服务技术融合了卫星导航、移动通信、Internet和数据库等当今IT行业的各种技术,形成一个独具特色、前景无限的新兴产业。随着全球定位系统、无线通信网络等基础设施的飞速发展和普及,面向位置服务的移动数据库技术已远不能满足用户不断增长的应用需求,面临着许多新的挑战。移动环境下,支持位置服务的移动对象数据库负责管理移动对象如汽车、飞机、舰船等位置信息,并提供相关查询服务。目前移动对象数据库领域的研究处于初步阶段,在理论和实际应用上还不成熟,存在许多问题和技术需要解决。
针对移动对象当前和未来位置的索引技术和移动环境下的查询处理技术得到了国内外研究者的广泛关注,是充满挑战性的研究方向。论文研究目的是针对目前移动对象数据库领域中的研究难点和热点,在全面总结和分析国内外数据库领域相关工作的基础上,面向遥感卫星监视系统应用需要,对移动对象数据库系统的关键技术:移动对象索引技术、连续k近邻查询处理技术和预测范围聚集查询处理技术进行研究,力图进行创新,并将相关研究成果应用于实际系统中。本文的主要工作和创新点包括下面几个方面:
(1)针对目前广泛使用的TPR树移动对象当前和未来位置索引在频繁更新应用中更新性能低下的问题,借鉴了R树BU算法思想,提出一种支持频繁更新的移动对象混合索引结构HTPR-tree,并给出了扩展的自底向上更新算法和更新代价模型。
(2)深入分析TPR树索引查询性能随着时间变化急遽下降的问题,提出了一种基于速度分布的移动对象混合索引HVTPR树索引。HVTPR树索引综合考虑移动对象在速度域和空间域中的分布进行构建,具有良好的预测查询性能。
(3)针对连续k近邻查询,引入了一种新的时空距离度量最小最大距离函数作为TPR树索引搜索时节点剪枝上界。提出了一种采用最优优先搜索策略的基于扩展时空距离度量的连续k近邻查询(STM-CNN)算法。STM-CNN算法利用最小距离函数进行TPR树索引节点搜索时访问排序,并使用最小最大距离函数对TPR树索引进行剪枝界定提高连续k近邻查询的搜索性能。
(4)研究基于TPR树索引的大量并发连续k近邻查询处理技术,提出了一种可伸缩的增量连续k近邻查询处理SI-CNN框架,通过引入搜索区域进行裁剪以减少查询更新的所需要的磁盘访问代价,并引入了增量结果表批量的更新查询结果集。基于SI-CNN框架提出了一种支持更新的SI-CNN查询处理算法,基于上次查询结果增量的更新查询且支持查询集合中加入或删除查询和移动对象数据集的插入、删除等动态更新操作。
(5)研究面向移动对象的精确预测范围聚集查询处理技术,提出了一种高效预测范围聚集查询索引(aTPR-tree)方法。通过在TPR树中间节点中加入聚集信息以减少预测范围聚集查询所需要的节点访问代价。aTPR树索引增加了一个建于叶节点之上的Hash辅助索引结构,并采用自底向上的删除搜索算法,具有很好的动态性能和并发性。基于aTPR树索引,提出了一种增强预测范围聚集查询(EPRA)算法,采用更精确的剪枝搜索准则,大大减少了查询所需要访问的节点代价。
基于上述研究成果,论文最后构建了遥感卫星目标监视查询处理引擎原型系统和城市应急联动位置服务实验系统,验证了移动对象索引、连续k近邻及预测范围聚集查询技术的有效性和实用性。
Location-based services provide users with services related to their positions which can be obtained through mobile devices and wireless networks infrastructure.The location-based services combine techniques in IT areas such as satellite navigation,mobile communications,internet and databases,thus have been becoming a unique and promising domain.With the repaid development of global positioning system(GPS),wireless cellular network,the moving objects databases techniques towards location-based services cannot meet the needs of users and face many challenges.
In dynamic environment,the moving objects databases manage the positions of moving objects such as vehicles,airplanes and fleets,and provide location-dependent queries. Currently the researches in moving objects databases are preliminary and far from maturation both in theory and practice.And there are many open problems to solve.
The indexing methods for current and future positions of moving objects and query techniques in dynamic environment,which are challenging directions,have been focused on by many researchers.In order to study the difficult and hot issues in moving objects databases,this paper gives comprehensive discusses and analysis on former work in related areas.And towards the application needs of satellite reconnaissance,this paper studies the key techniques in moving objects databases including indexing methods on moving objects, techniques of continuous k nearest neighbors query and predicted range aggregate query, and apply our achievements to practical applications.The main work and innovations are detailed as follows:
1.A hybrid indexing method,HTPR-tree,which is based on TPR-tree and supplemented by a hash index,is presented to improve the lower performance of TPR-tree with frequent updates.Motivate by the bottom-up strategy of R-tree,an extended bottom-up update algorithm is developed for HTPR-tree and its cost model is also given.
2.Based on thorough analysis on the query performance degrade of TPR-tree,we present a hybrid velocity distribution based time-parameterized R-tree(HVTPR-tree),which takes into account the distribution of both velocity domain and space domain and thus have a good query performance.
3.In order to process continuous k nearest neighbors query based on TPR-tree efficiently,we present a new spatio-temporal distance metrics minmaxdist(t) as a pruning upper bound.Also a query algorithm based on extended spatio-temporal metrics (STM-CNN),searching in best-first manner,is developed.STM-CNN algorithm visits TPR-tree nodes according to mindist(t) order,and pruning the nodes with minmaxdist(t) to improve the query performance.
4.To evaluate large collection of concurrent continuous k nearest neighbors queries continuously,we propose a scalable processing of incremental continuous k-nearest neighbor(SI-CNN) framework by introducing searching region to filter the visiting TPR-tree nodes.SI-CNN framework exploits incremental results table to buffer candidate objects and flushes the objects into query results in bulk.We then present an incremental SI-CNN query update algorithm,which evaluates incrementally based on former query answers and supports insertion or deletion of both query collection and moving objects.
5.To improve the query performance of accurate predictive range aggregate(PRA) queries,we present an efficient predicted aggregate time-parameterized R-tree(aTPR-tree), which is based on TPR-tree structure and added with aggregate information in intermediate nodes to reduce the disk accesses of PRA queries.The aTPR-tree is supplemented by a hash index on leaf nodes,and uses bottom-up delete algorithm,thus having a good update performance and concurrency.Also an Enhanced predictive range aggregate(EPRA) query algorithm which uses a more precise branch and bound searching strategy is developed for aTPR-tree,reducing the node accesses greatly.
Based on the above achievements,we design a remote sensing satellite targets reconnaissance query engine prototype and a location-based services experimental system fbr city emergency linkage to validate the efficiency and practice of our presented techniques including moving objects indexing methods,continuous k nearest neighbor query and predicted range aggregate query.
针对移动对象当前和未来位置的索引技术和移动环境下的查询处理技术得到了国内外研究者的广泛关注,是充满挑战性的研究方向。论文研究目的是针对目前移动对象数据库领域中的研究难点和热点,在全面总结和分析国内外数据库领域相关工作的基础上,面向遥感卫星监视系统应用需要,对移动对象数据库系统的关键技术:移动对象索引技术、连续k近邻查询处理技术和预测范围聚集查询处理技术进行研究,力图进行创新,并将相关研究成果应用于实际系统中。本文的主要工作和创新点包括下面几个方面:
(1)针对目前广泛使用的TPR树移动对象当前和未来位置索引在频繁更新应用中更新性能低下的问题,借鉴了R树BU算法思想,提出一种支持频繁更新的移动对象混合索引结构HTPR-tree,并给出了扩展的自底向上更新算法和更新代价模型。
(2)深入分析TPR树索引查询性能随着时间变化急遽下降的问题,提出了一种基于速度分布的移动对象混合索引HVTPR树索引。HVTPR树索引综合考虑移动对象在速度域和空间域中的分布进行构建,具有良好的预测查询性能。
(3)针对连续k近邻查询,引入了一种新的时空距离度量最小最大距离函数作为TPR树索引搜索时节点剪枝上界。提出了一种采用最优优先搜索策略的基于扩展时空距离度量的连续k近邻查询(STM-CNN)算法。STM-CNN算法利用最小距离函数进行TPR树索引节点搜索时访问排序,并使用最小最大距离函数对TPR树索引进行剪枝界定提高连续k近邻查询的搜索性能。
(4)研究基于TPR树索引的大量并发连续k近邻查询处理技术,提出了一种可伸缩的增量连续k近邻查询处理SI-CNN框架,通过引入搜索区域进行裁剪以减少查询更新的所需要的磁盘访问代价,并引入了增量结果表批量的更新查询结果集。基于SI-CNN框架提出了一种支持更新的SI-CNN查询处理算法,基于上次查询结果增量的更新查询且支持查询集合中加入或删除查询和移动对象数据集的插入、删除等动态更新操作。
(5)研究面向移动对象的精确预测范围聚集查询处理技术,提出了一种高效预测范围聚集查询索引(aTPR-tree)方法。通过在TPR树中间节点中加入聚集信息以减少预测范围聚集查询所需要的节点访问代价。aTPR树索引增加了一个建于叶节点之上的Hash辅助索引结构,并采用自底向上的删除搜索算法,具有很好的动态性能和并发性。基于aTPR树索引,提出了一种增强预测范围聚集查询(EPRA)算法,采用更精确的剪枝搜索准则,大大减少了查询所需要访问的节点代价。
基于上述研究成果,论文最后构建了遥感卫星目标监视查询处理引擎原型系统和城市应急联动位置服务实验系统,验证了移动对象索引、连续k近邻及预测范围聚集查询技术的有效性和实用性。
Location-based services provide users with services related to their positions which can be obtained through mobile devices and wireless networks infrastructure.The location-based services combine techniques in IT areas such as satellite navigation,mobile communications,internet and databases,thus have been becoming a unique and promising domain.With the repaid development of global positioning system(GPS),wireless cellular network,the moving objects databases techniques towards location-based services cannot meet the needs of users and face many challenges.
In dynamic environment,the moving objects databases manage the positions of moving objects such as vehicles,airplanes and fleets,and provide location-dependent queries. Currently the researches in moving objects databases are preliminary and far from maturation both in theory and practice.And there are many open problems to solve.
The indexing methods for current and future positions of moving objects and query techniques in dynamic environment,which are challenging directions,have been focused on by many researchers.In order to study the difficult and hot issues in moving objects databases,this paper gives comprehensive discusses and analysis on former work in related areas.And towards the application needs of satellite reconnaissance,this paper studies the key techniques in moving objects databases including indexing methods on moving objects, techniques of continuous k nearest neighbors query and predicted range aggregate query, and apply our achievements to practical applications.The main work and innovations are detailed as follows:
1.A hybrid indexing method,HTPR-tree,which is based on TPR-tree and supplemented by a hash index,is presented to improve the lower performance of TPR-tree with frequent updates.Motivate by the bottom-up strategy of R-tree,an extended bottom-up update algorithm is developed for HTPR-tree and its cost model is also given.
2.Based on thorough analysis on the query performance degrade of TPR-tree,we present a hybrid velocity distribution based time-parameterized R-tree(HVTPR-tree),which takes into account the distribution of both velocity domain and space domain and thus have a good query performance.
3.In order to process continuous k nearest neighbors query based on TPR-tree efficiently,we present a new spatio-temporal distance metrics minmaxdist(t) as a pruning upper bound.Also a query algorithm based on extended spatio-temporal metrics (STM-CNN),searching in best-first manner,is developed.STM-CNN algorithm visits TPR-tree nodes according to mindist(t) order,and pruning the nodes with minmaxdist(t) to improve the query performance.
4.To evaluate large collection of concurrent continuous k nearest neighbors queries continuously,we propose a scalable processing of incremental continuous k-nearest neighbor(SI-CNN) framework by introducing searching region to filter the visiting TPR-tree nodes.SI-CNN framework exploits incremental results table to buffer candidate objects and flushes the objects into query results in bulk.We then present an incremental SI-CNN query update algorithm,which evaluates incrementally based on former query answers and supports insertion or deletion of both query collection and moving objects.
5.To improve the query performance of accurate predictive range aggregate(PRA) queries,we present an efficient predicted aggregate time-parameterized R-tree(aTPR-tree), which is based on TPR-tree structure and added with aggregate information in intermediate nodes to reduce the disk accesses of PRA queries.The aTPR-tree is supplemented by a hash index on leaf nodes,and uses bottom-up delete algorithm,thus having a good update performance and concurrency.Also an Enhanced predictive range aggregate(EPRA) query algorithm which uses a more precise branch and bound searching strategy is developed for aTPR-tree,reducing the node accesses greatly.
Based on the above achievements,we design a remote sensing satellite targets reconnaissance query engine prototype and a location-based services experimental system fbr city emergency linkage to validate the efficiency and practice of our presented techniques including moving objects indexing methods,continuous k nearest neighbor query and predicted range aggregate query.
引文
[1]Christian S.Jensen,Anders Friis Christensen,Torben B.Pedersen,Dieter Pfoser,Simonas Saltenis,and Nectaria Tryfona.Location-Based Services-A Database Perspective.In Proceedings of the Eighth Scandinavian Research Conference on Geographical Information Science,pages 59-68,Norway,June 2001.
[2]曹冲.位置服务:多个产业的交会点.hup://www.ccw.com.cn/
[3]丁治明.移动数据库关键技术研究.博士论文.中国人民大学.2002.
[4]杨菠.定位服务:3G时代的新杀手应用.http://www.ccw.com.cn/
[5]LBS software and solution providers,http://www.lbszone.com/
[6]Ouri Wolfson,and Eduardo Mena.Applications of Moving Objects Databases.Spatial Databases:Technologies,Techniques and Trends,Idea Group,2005.
[7]陈良刚.移动计算环境中位置相关数据管理.博士论文.复旦大学.2003.
[8]Ouri Wolfson.Moving Objects Information Management:The Database Challenge.In Proceedings of the 5th International Workshop on Next Generation Information Technologies and Systems,pages 75-89,London,2002.
[9]John F.Roddick,Max J.Egenhofer,Erik Hoel,and Dimitris Papadias.Spatial,Temporal and Spatio-Temporal Databases-Hot Issues and Directions for PhD Research.ACM SIGMOD Record,33(2),2004.
[10]EPEL,U.Grenoble,INRIA-Nancy,INT-Evry,U.Montpellier,U.Paris,and U.Versailles.Mobile Databases:A Selection of Open Issues and Research Directions.ACM SIGMOD Record,33(2),2004.
[11]Zhiyuan Chen,Chen Li,Jian Pei,Yufei Tao,Haixun Wang,Wei Wang,Jiong Yang,Jun Yang,and Donghui Zhang.Recent Progress on Selected Topics in Database Research A Report from Nine Young Chinese Researchers Working in the United States.Chinese Journal of Computer Science and Technology,2004.
[12]孟小峰,周龙骥,王珊.数据库技术发展趋势.软件学报.2004,15(12):1822-1836.
[13]Ouri Wolfson,S.Chamberlain,S.Dao,and L.Jiang.Location Management in Moving Objects Databases.In Proceedings of the 2rid International Workshop on Satellite-Based Information Services(WOSBIS),pages 7-14,Budapest,Hungary,1997.
[14]Ouri Wolfson,B.XU,S.Chamberlain,L.Jung,Moving Object Databases:Issues and Solutions.In Proceedings of the 10th International Conference on Science and Statistical Database Management,pages 111-122,Capri,Italy,July 1998.
[15]A.P.Sistla,Ouri Wolfson.S.Chmbexlian,and S.Dao.Modeling and Querying Moving Objects.In Proceedings of International Conference on Data Engineering (ICDE),1997.
[16]Rafanelli M.Multidimensional Databases:Problems and Solutions.Idea Group Publishing,Hershey,PA.2003.
[17]Jensen CS.Research Challenges in Location-Enabled Services.In Proceedings of the 3rd International Conference on Mobile Data Management(MDM),Singapore,pages 8-11,2002.
[18]Guting,R.H.Bohlen,M.H.Erwig,M.Jensen,C.S.Lorentzos,N.A.Schneider,and M.Vazirgiannis.A Foundation for Representing and Querying Moving Objects.ACM Transactions on Database Systems(TODS),25(1):1-42.2000.
[19]Pitoura E.and Samaras G.Locating Objects in Mobile Computing.IEEE Transactionss on Knowledge and Data Engineering(TKDE),13(4),2001.
[20]Jensen CS,Kligys A.,Pedersen TB,and Timko I.Multidimensional Data Modeling for Location-Based Services.In Proceedings of the 10th ACM International Symposium on Advances in Geographic Information Systems(ACM-GIS),pages 55-61,2002.
[21]Guting RH,B(o|¨)hlen MH,Erwig M,Jensen CS,Lorentzos NA,Schneider M,and Vazirgiannis M.A Foundation for Representing and Querying Moving Objects.ACM Transactions on Database Systems(TODS),25(1):1-42,2000.
[22]E.Pitoura and G.Samaras.Locating Objects in Mobile Computing.IEEE Transactionss on Knowledge and Data Engineering(TKDE),13(4),2001.
[23]Luca Forlizzi,Ralf Hartmut Guting.A Data Model and Data Structures for Moving Objects Databases.In Proceeding of ACM International Conference on Management of Data(SIGMOD),2000.
[24]Birgitta K(o|¨)nig-Ries,Kia Makki.Research Direction for Developing an Infrastructure for Mobile & Wireless Systems.Consensus Report of the NSF Workshop,2001.
[25]H.D.Chon,D.Agrawal,and A.E.Abbadi.Storage and Retrieval of Moving Objects.In Proceedings of the 2nd International Conference on Mobile Data Management (MDM),2001.
[26]Ouri Wolfson and Bo Xu.Moving Objects Databases:Issues and Solutions.In Proceedings of International Conference on Scientific and Statistical Database Management(SSDBM),1998.
[27]Y Manolopoulos,A.Nanopoulos,and AN.Papadopoulos.R-trees Have Grown Everywhere.ACM Computing Surveys,2003.
[28]廖巍,熊伟,景宁,陈宏盛.移动对象索引技术研究进展.计算机科学.33(8):166-169,2006.
[29]R.Laurini and D.Thomson.Fundamentals of Spatial Information Systems.Academic Press,London,1992.
[30]Shashi Shekhar and Sanjay Chawla.Spatial Database:A Tour.Pearson Education,2003.
[31]Guttman.R-Trees:A Dynamic Index Structure for Spatial Searching.In Proceedings of the ACM Intentional Conference on Management of Data(SIGMOD),pages 47-57,1984.
[32]N.Beckmann,H.P.Kriegel,R.Schneider and B.Seeger.The R*-tree:An Efficient and Robust Method for Points and Rectangles.In Proceeding of the ACM Intentional Conference on Management of Data(SIGMOD),pages 322-331,1990.
[33]S.Berchtold,D.A.Keim and H.P.Kriegel.The X-tree:An Index Structure for High-Dimensional Data.In Proceeding of the 22nd International Conference on Very Large Databases(VLDB),pages 28-39,1996.
[34]Nievergelt J.,Hinterberger H.,and Sevcik K.The Grid File:An Adaptable,Symmetric Multikey File Structure.ACM Transactionss on Database Systems(TODS),9(1):38-71,1984.
[35]Mohamed F.,Mokbel Thanaa,M.Ghanem,and Walid G.Aref.Spatio-temporal Access Methods.IEEE Data Engineering Bulletin,2003.
[36]Pedersen TB.Aspects of Data Modeling and Query Processing for Complex Multidimensional Data.Ph.D.Thesis,Aalborg University,Analogist,Denmark,2000.
[37]Pedersen TB,Jensen CS,and Dyreson CE.A Foundation for Capturing and Querying Complex Multidimensional Data.Information System,26(5):383-423,2001.
[38]Rafanelli M.and Shoshani A.STORM:A Statistical Object Representation Model.In Proceedings of the 5th International Conference on Statistical and Scientific Database Management(SSDBM),pages 14-29,1990.
[39]0.Wolfson,L.Jiang,A.P.Sistla,S.Chamberlain,and M.Deng.Updating and Querying Databases that Track Mobile Units.Distributed and Parallel Databases,7(6):257-387,1998.
[40]Pfoser D.and Jensen,C.S.Capturing the Uncertainty of Moving Objects Representations.In Proceedings of the 12th International Conference on Scientific and Statistical Database Management(SSDBM),2000.
[41]Pedersen,T.B.,Jensen,C.S.,and Dyreson C.E.Supporting Imprecision in Multidimensional Databases Using Granularities.In Proceedings of the 11th International Conference on Scientific and Statistical Database Management(SSDBM),pages 90-101,1999.
[42]张明波,陆峰,申排伟,程昌秀.R树家族的演变和发展.计算机学报.28(3):289-300,2005.
[43]X.Xu,J.Han and W.Lu.RT-Tree:An Improved R-Tree Indexing Structure for Temporal Spatial Databases.In Proceedings of the International Symposium on Spatial Data Handling(SDH),1990
[44]D.B.Lomet and B.Salzberg.Access Methods for Multiversion Data.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),pages 315-324,1989.
[45]Y.Theodoridis,M.Vazirgiannis,and T.Sellis.Spatio-Temporal Indexing for Large Multimedia Applications.In Proceedings of the IEEE Conference on Multimedia Computing and Systems(ICMCS),1996.
[46]S.Leutenegger,J.M.Edgington and M.A.Lopez.STR:A Simple and Efficient Algorithm for R-tree Packing.In Proceedings of the 13th IEEE Conference on Data Engineering(ICDE),pages 497-506,1997.
[47]M.A.Nascimento and J.R.O.Silva.Towards Historical R-trees.In Proceedings of the ACM Symposium on Applied Computing(SAC),1998.
[48]Y.Tao and D.Papadias.MV3R-Tree:A Spatio-Temporal Access Method for Timestamp and Interval Queries.In Proceedings of the International Conference on Very Large Databases(VLDB),2001.
[49]Y.Tao and D.Papadias.Efficient Historical R-trees.In Proceedings of the International Conference on Scientific and Statistical Database Management(SSDBM),pages 223-232,2001.
[50]G.Kollios,V.J.Tsotras,D.Gunopulos,A.Delis,and M.Hadjieleftheriou.Indexing Animated Objects Using Spatiotemporal Access Methods.IEEE Transactions on Knowledge and Data Engineering(TKDE),13(5):758-777,2001.
[51]V.P.Chakka,A.Everspaugh,and J.M.Patel.Indexing Large Trajectory Data Sets with SETI.In Proceedings of CIDR 2003.
[52]Z.Song and N.Roussopoulos.SEB-tree:An Approach to Index Continuously Moving Objects.In Proceedings of the International Conference on Mobile Data Management (MDM),2003.
[53]D.Pfoser,C.S.Jensen,and Y.Theodoridis.Novel Approaches in Query Processing for Moving Object Trajectories.In Proceedings of the International Conference on Very Large Databases(VLDB),pages 395-406,2000.
[54]M.A.Nascimento,J.R.O.Silva,and Y.Theodoridis.Evaluation of Access Structures for Discretely Moving Points.In Proceedings of the International workshop on Spatio-temporal Database Management(STDBM),1999.
[55]D.Kwon,S.Lee,and S.Lee.Indexing the Current Positions of Moving Objects Using the Lazy Update R-tree.In Proceedings of the International Conference on Mobile Data Management(MDM),2002.
[56]M.Lee,W.Hsu,C.Jensen,B.Cui,and K.Teo.Supporting Frequent Updates in R-Trees:A Bottom-Up Approach.In Proceedings of the International Conference on Very Large Databases(VLDB),2003.
[57]Z.Song and N.Roussopoulos.Hashing Moving Objects.In Proceedings of the International Conference on Mobile Data Management(MDM),2001.
[58]J.Tayeb,O.Ulusoy,and O.Wolfson.A Quadtree-Based Dynamic Attribute Indexing Method.The Computer Journal,1998.
[59]Christian S.Jensen,Dan Lin,and Beng Chin Ooi.Query and Update Efficient B+-tree Based Indexing of Moving Objects.In Proceedings of the International Conference on Very Large Databases(VLDB),2004.
[60]B.Moon,H.V.Jagadish,C.Faloutsos,and J.H.Saltz.Analysis of the Clustering Properties of the Hilbert Space-Filling Curve.IEEE Transactions on Knowledge and Data Engineering(TKDE),13(1):124-141,2001.
[61]G.Kollios,D.Gunopulos,and V.J.Tsotras.On Indexing Mobile Objects.In Proceedings of A CM PODS 1999.
[62]H.D.Chon,D.Agrawal,and A.E.Abbadi.Storage and Retrieval of Moving Objects.Proceedings of Proceedings of the International Conference on Mobile Data Management(MDM),2001.
[63]D.A.White and R.Jain.Similarity.Indexing with the SS-tree.In Proceedings of the International Conference on Data Engineering(1CDE),pages 516-523,1996.
[64]K.Porkaew,I.Lazaridis,and S.Mehrotra.Querying Mobile Objects in Spatio-Temporal Databases.In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases(SSTD),pages 59-78,2001.
[65]Jignesh M.,Patel Yun,Chen V.,and Prasad Chakka.STRIPES:An Efficient Index for Predicted Trajectories.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),2004.
[66]S.Saltenis,C.S.Jensen,S.T.Leutenegger,and M.A.Lopez.Indexing the Positions of Continuously Moving Objects.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),2000.
[67]Tao,Y.,Papadias D.and Sun,J.The TPR*-Tree:An Optimized Spatio-Temporal Access Method for Predictive Queries.In Proceedings of the International Conference on Very Large Databases(VLDB),2003.
[68]S.Prabhakar,Y.Xia,D.V.Kalashnikov,W.G.Aref,and S.E.Hambrusch.Query Indexing and Velocity Constrained Indexing:Scalable Techniques for Continuous Queries on Moving Objects.IEEE Transactions on Computers,2002.
[69]C.M.Procopiuc,P.K.Agarwal,and S.Har-Peled.STAR-Tree:An Efficient Self-Adjusting Index for Moving Objects..In Proceedings of the Workshop on Alg.Eng.and Experimentation,ALENEX,pages 178-193,Jan.2002.
[70]M.Cai and P.Revesz,Parametric R-Tree:An Index Structure for Moving Objects.In Proceedings of the International Conference on Management of Data(COMAD),2000.
[71]S.Saltenis and C.S.Jensen.Indexing of Moving Objects for Location-Based Services.In Proceedings of the International Conference on Data Engineering(1CDE),2002.
[72]Y Tao,C Faloutsos,D Papadias,and B Liu.Prediction and Indexing of Moving Objects with Unknown Motion Patterns.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),2004.
[73]A.K.Agarwal,L.Arge,and J.Ericskon.Indexing moving points.In Proceedings of ACM PODS 2000.
[74]Hae Don Chon,Divyakant Agrawal,and Amr El Abbadi.Data Management for Moving Objects.In Proceeding of International Telematics and LBS Workshop,2003.
[75]Jimeng Sun,Dimitris Papadias,Yufei Tao,Bin Liu.Querying about the Past,the Present,and the Future in Spatio-Temporal Databases.In Proceedings of the International Conference on Data Engineering(ICDE),2004.
[76]Shekhar S.and Liu D.CCAM:A Connectivity-Clustered Access Method for Networks and Network Computations.IEEE Transactions on Knowledge and Data Engineering (TKDE),19(1):102-119,1997.
[77]Huang Y.,Jing N.,and Rundensteiner,E.Integrated Query Processing Strategies for Spatial Path Queries.In Proceedings of the International Conference on Data Engineering(1CDE),1997.
[78]Yufei Tao and Papadias D.Time-Parameterized Queries in Spatio-Temporal Databases.In Proceedings of the ACM International Conference on Management of Data (SIGMOD),2002.
[79]Jun Zhang,Manli Zhu,Dimitirs Papadias,Yufei Tao,and Dik Lun Lee.Location-based Spatial Queries.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),2003.
[80]F.Korn and S.Muthukrishnan.Influence Sets Based on Reverse Nearest Neighbor Queries.In Proceedings of the ACM lnternational Conference on Management of Data (SIGMOD),pages 201-212,2000.
[81]Roussopoulos N.and Kelly S.Vincent F.Nearest Neighbor Queries.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),1995.
[82]Papadoulos and Y.Manolopoulos.Performance of Nearest Neighbor Queries in R-trees.In Proceedings of International Conference on Database Theory(1CDT),pages 394-408,1997.
[83]K.L.Cheung and A.W.fu.Enhanced Nearest Neighbor Search on the R-tree.ACM SIGMOD Record,27(3):16-21,1998.
[84]H.Samet,and G.Hjaltason.Distance Browsing in Spatial Databases.ACM Transactions on Database Systems(TODS),24(2):265-318,1999.
[85]Zheng B.and Lee D.Semantic Caching in Location Dependent Query Processing.In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases(SSTD),2001.
[86]Okabe A.,Boots B.,Sugihara K.,and Chiu S.Spatial Tessellations:Concepts and Applications of Voronoi Diagrams,John Wildy,2000.
[87]Song,Z.and Roussopoulos N.K-Nearest Neighbor Search for Moving Query Point.In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases(SSTD),2001.
[88]Tao Y.,Papadias D.,and Shen Q.Continuous Neighbor Search.In Proceedings of the International Conference on Very Large Databases(VLDB),2002.
[89]Rimantas Benetis,Christian S.Jensen,Gytis Karciauskas,and Simonas Saltenis.Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects.In Proceedings of the International Database Engineering and Applications Symposium (IDEAS),2002.
[90]Yufei Tao and Dimitris Papadias.Spatial Queries in Dynamic Environment.ACM Transactions on Database Systems(TODS),2003.
[91]Glenn S.Iwerks,Hanan Samet,and Kenneth P.Smith.Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates.In Proceedings of 29th International Conference on Very Large Databases(VLDB),2003.
[92]Mohamed F.Mokbel,Xiaopeng Xiong,and Walid G.Aref.SINA:Scalable Incremental Processing of ContinuousQueries in Spatiotemporal Databases.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),2004.
[93]Xiaopeng Xiong,Mohamed F.Mokbel and 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(ICDE),2005.
[94]Xiaohui Yu,Ken Q.Pu,and Nick Koudas.Monitoring k-Nearest Neighbor Queries over Moving Objects.In Proceedings of the 21st International Conference on Data Engineering(ICDE),2005.
[95]Kyriakos Mouratidis,Marios Hadjieleftherious,and Dimitris Papadias.Conceptual Partitioning:An Efficient Method for Continuous Nearest Neighbor Monitoring.In Proceedings of the ACM International Conference on Managemeni of Data(SIGMOD),2005.
[96]C.S.Jensen,J.Kolrvr,Y.B.Pedersen,and I.Timko.Nearest Neighbor Queries in Road Networks.In Proceedings of the llth ACM International Symposium on Advances in Geographic Information Systems(ACM-GIS),2003.
[97]M.Kolahdouzan and C.Shahabi.Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases.In Proceedings of 29th International Conference on Very Large Databases(VLDB),2004.
[98]D.Papadias,J.Zhang,N.Mamoulis,and Y.Tao.Query Processing in Spatial Network Databases.In Proceedings of 29th International Conference on Very Large Databases (VLDB),2003.
[99]Mohammad R.Kolahdouzan and Cyrus Shahabi.Continuous K Nearest Neighbor Queries in Spatial Network Databases.Proceedings of the International workshop on Spatio-temporal Database Management(STDBM),2004.
[100]Shahabi,C.,Kolahdouzan,M.,Sharifzadeh,M.A Road Network Embedding Technique for K Nearest Neighbor Search in Moving Object Databases.In Proceedings of the 11th ACM International Symposium on Advances in Geographic Information Systems(ACM-GIS),2002.
[101]J.Feng and T.Watanabe.A Fast Method for Continuous Nearest Target Objects Query on Road Network.In VSMM'02 pages 182-191 Sept.2002,Korea.
[102]S.Jung and S.Pramanik.An Efficient Path Computation Model for Hierarchically Structured Topological Road Maps.IEEE Transactions on Knowledge and Data Engineering(TKDE),2002.
[103]Ine's Fernando Vega Lo'pez,Richard T.Snodgrass,Spatiotemporal Aggregate Computation:A Survey.IEEE Transactions on Knowledge and Data Engineering (TKDE);17(2):271-286,2005.
[104]Y.Tao,G.Kollios,J.Considine,F.Li,and D.Papadias,Spatio-Temporal Aggregation Using Sketches.In Proceedings of the 21st International Conference on Data Engineering(ICDE),pages 214-226,2004.
[105]Yufei Tao,Dimitris Papadias,Jian Zhai,and Qing Li.Venn Sampling:A Novel Prediction Technique for Moving Objects.In Proceedings of the 21st International Conference on Data Engineering(ICDE),2005.
[106]Yufei Tao,Jimeng Sun,and Dimitris Papadias.Selectivity Estimation for Predictive Spatio-Temporal Queries.In Proceedings of the 21st International Conference on Data Engineering(ICDE),2003.
[107]Choi Y.,Chung C.Selectivity Estimation for Spatio-temporal Queries to Moving Objects.In Proceedings of the ACM lnternational Conference on Management of Data (SIGMOD),2002.
[108]Hadjieleftheriou M.,Kollios G.,and Tsotras V.Performance Evaluation of Spatio-temporal Selectivity Estimation Techniques.In Proceedings of the International Conference on Scientific and Statistical Database Management(SSDBM),2003.
[109]Dimitris Papadias,Yufei Tao,Kalnis P.,and Zhang J.Indexing Spatio-temporal Data Warehouse.In Proceedings of the 21st International Conference on Data Engineering(ICDE),2002.
[110]Y.Tao,Jimeng Sun,and Dimitris Papadias.Analysis of Predictive Spatio-Temporal Queries.ACM Transactions on Database Systems(TODS),28(4):295-336,2003.
[111]Yufei Tao,Dimitris Papadias,and X.Lian.Reverse kNN Search in Arbitrary Dimensionality.In Proceedings of 29th International Conference on Very Large Databases(VLDB),2004.
[112]Amit Singh,Hakan Ferhatosmanoglu,and Ali Saman Tosun.High Dimensional Reverse Nearest Neighbor Queries.In Proceedings of the 12th ACM International Conference on Information and knowledge Management(CI~,pages:91-98,2003.
[113]Chenyi Xia,Wynne Hsu,and Mong Li Lee.ERkNN:Efficient Reverse k-Nearest Neighbors Retrieval with Local kNN-Distance Estimation.In Proceedings of the 14th ACM International Conference on Information and knowledge Management(CIKM),pases 533-540,2005.
[114]Like Achtert,Christian B(¨)hm,and Peer Kr(o|¨)ger.Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),pages 515-526,2006.
[115]Man Lung Yiu,Dimitris Papadias,Nikos Mamoulis,and Yufei Tao.Reverse Nearest Neighbors in Large Graphs.IEEE Transactions on Knowledge and Data Engineering(TKDE),18(4):540-553,2006.
[116]Dimitris Papadias,Shen Q.,Yufei Tao,Mouratidis K.Group Nearest Neighbor Queries.In Proceedings of the 21st International Conference on Data Engineering (ICDE),2004.
[117]Ferhatosmanoglu H.,Stanoi I.,Agrawal D.,and Abbadi A.Constrained Nearest Neighbor Queries.In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases(SSTD),2001.
[118]G.S.Iwerks,H.Samet,and K.Smith.Maintenance of Spatial Semi-join Queries on Moving Points.Proceedings of 29th International Conference on Very Large Databases(VLDB),2004.
[119]Andrew Noske.Efficient Algorithms for Molecular Dynamics Simulations and Other Dynamic Spatial Join Queries.Ph.D.Thesis,Department of Information Technology,James Cook University,2004.
[120]熊伟,廖巍,陈宏盛,景宁.空间数据库中距离连接选择率估计方法研究.计算机学报.29(1):45-53.2006.
[121]熊伟,廖巍,张帆,景宁,陈宏盛.空间连接处理中提炼步骤地遗传优化.电子学报.34(6):1069-1073.2006.
[122]廖巍,熊伟,景宁,陈宏盛,钟志农.支持频繁更新的移动对象混合索引方法.计算机研究与发展.43(5):888-893.2006.
[123]熊伟,廖巍,陈宏盛,景宁.空间数据库主动规则行为控制研究.计算机研究与发展.43(8):888-893.2006.
[124]Http://www.census.gov/geo/www/tiger
[125]Yuni Xia,Sunil Prabhakar,Q+Rtree:Efficient Indexing for Moving Object Databases.Proceeding of 2003 International Conference on Database Systems for Advanced Applications.Pages:175-182,2003.
[126]Bin Lin and Jianwen Su.On Bulk Loading TPR-Tree.In Proceedings of the International Conference on Mobile Data Management(MDM),2004.
[127]Liaowei,Tangguifen,Jingning,and Zhongzhinong.VTPR-tree An Efficient Indexing Method for Moving Objects with Frequent Updates.In Proceedings of the International ER Workshop on Conceptual Modeling for Geographic Information Systems,(CoMoGIS),2006.
[128]廖巍,唐桂芬,景宁,钟志农.基于速度分布的移动对象混合索引方法.计算 机学报.2006,(录用).
[129]Haibo Hu,Jianliang Xu,and Dik Lun Lee.A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects.In Proceedings of the International Conference on Management of Data(SIGMOD).pages 479-490,2005.
[130]廖巍,唐桂芬,景宁,陈宏盛.基于扩展时空距离度量的连续k近邻查询方法.国防科技大学学报,2006,已投.
[131]廖巍,熊伟,王钧,景宁,钟志农.可伸缩的增量连续k邻近查询方法.软件学报.2006,(录用).
[132]Brinkhoff T.A Framework for Generating Network-based Moving Objects.Geolnformatica.(6)2:153-180,2002.
[133]Hicham G.Elmongui,Mohamed F.Mokbel,and Walid G.Aref.Spatio-temporal Histograms.In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases(SSTD),2005.
[134]Q.Zhang and X.Lin.Clustering Moving Objects for Spatio-temporal Selectivity Estimation.In Proceedings of the 15th International Conference on Australasian Database(CRPIT),pages 123-130.Australian Computer Society,2004.
[135]M.Jurgens and H.Lenz.The Ra*-Tree:An Improved R-Tree with Materialized Data for Supporting Range Queries on OLAP-Data.In Proceedings of the DEXA Workshop,1998.
[136]Tao Yufei and Dimitris Papadias.Historical Spatio-temporal Aggregation.ACM Transactions on Information Systems.(23) 1:61-102.2005.
[137]Liao Wei,Tang Guifen,Jing Ning,and Zhong Zhinong.Predicted Range Aggregate Processing in Spatio-temporal Databases.In Proceedings of the 3rd International VLDB workshop on Spatio-temporal Database Management(STDBM),2006.
[138]廖巍,唐桂芬,景宁,钟志农.面向移动对象的高效预测范围聚集查询方法.计算机研究与发展.2006,已投.
[2]曹冲.位置服务:多个产业的交会点.hup://www.ccw.com.cn/
[3]丁治明.移动数据库关键技术研究.博士论文.中国人民大学.2002.
[4]杨菠.定位服务:3G时代的新杀手应用.http://www.ccw.com.cn/
[5]LBS software and solution providers,http://www.lbszone.com/
[6]Ouri Wolfson,and Eduardo Mena.Applications of Moving Objects Databases.Spatial Databases:Technologies,Techniques and Trends,Idea Group,2005.
[7]陈良刚.移动计算环境中位置相关数据管理.博士论文.复旦大学.2003.
[8]Ouri Wolfson.Moving Objects Information Management:The Database Challenge.In Proceedings of the 5th International Workshop on Next Generation Information Technologies and Systems,pages 75-89,London,2002.
[9]John F.Roddick,Max J.Egenhofer,Erik Hoel,and Dimitris Papadias.Spatial,Temporal and Spatio-Temporal Databases-Hot Issues and Directions for PhD Research.ACM SIGMOD Record,33(2),2004.
[10]EPEL,U.Grenoble,INRIA-Nancy,INT-Evry,U.Montpellier,U.Paris,and U.Versailles.Mobile Databases:A Selection of Open Issues and Research Directions.ACM SIGMOD Record,33(2),2004.
[11]Zhiyuan Chen,Chen Li,Jian Pei,Yufei Tao,Haixun Wang,Wei Wang,Jiong Yang,Jun Yang,and Donghui Zhang.Recent Progress on Selected Topics in Database Research A Report from Nine Young Chinese Researchers Working in the United States.Chinese Journal of Computer Science and Technology,2004.
[12]孟小峰,周龙骥,王珊.数据库技术发展趋势.软件学报.2004,15(12):1822-1836.
[13]Ouri Wolfson,S.Chamberlain,S.Dao,and L.Jiang.Location Management in Moving Objects Databases.In Proceedings of the 2rid International Workshop on Satellite-Based Information Services(WOSBIS),pages 7-14,Budapest,Hungary,1997.
[14]Ouri Wolfson,B.XU,S.Chamberlain,L.Jung,Moving Object Databases:Issues and Solutions.In Proceedings of the 10th International Conference on Science and Statistical Database Management,pages 111-122,Capri,Italy,July 1998.
[15]A.P.Sistla,Ouri Wolfson.S.Chmbexlian,and S.Dao.Modeling and Querying Moving Objects.In Proceedings of International Conference on Data Engineering (ICDE),1997.
[16]Rafanelli M.Multidimensional Databases:Problems and Solutions.Idea Group Publishing,Hershey,PA.2003.
[17]Jensen CS.Research Challenges in Location-Enabled Services.In Proceedings of the 3rd International Conference on Mobile Data Management(MDM),Singapore,pages 8-11,2002.
[18]Guting,R.H.Bohlen,M.H.Erwig,M.Jensen,C.S.Lorentzos,N.A.Schneider,and M.Vazirgiannis.A Foundation for Representing and Querying Moving Objects.ACM Transactions on Database Systems(TODS),25(1):1-42.2000.
[19]Pitoura E.and Samaras G.Locating Objects in Mobile Computing.IEEE Transactionss on Knowledge and Data Engineering(TKDE),13(4),2001.
[20]Jensen CS,Kligys A.,Pedersen TB,and Timko I.Multidimensional Data Modeling for Location-Based Services.In Proceedings of the 10th ACM International Symposium on Advances in Geographic Information Systems(ACM-GIS),pages 55-61,2002.
[21]Guting RH,B(o|¨)hlen MH,Erwig M,Jensen CS,Lorentzos NA,Schneider M,and Vazirgiannis M.A Foundation for Representing and Querying Moving Objects.ACM Transactions on Database Systems(TODS),25(1):1-42,2000.
[22]E.Pitoura and G.Samaras.Locating Objects in Mobile Computing.IEEE Transactionss on Knowledge and Data Engineering(TKDE),13(4),2001.
[23]Luca Forlizzi,Ralf Hartmut Guting.A Data Model and Data Structures for Moving Objects Databases.In Proceeding of ACM International Conference on Management of Data(SIGMOD),2000.
[24]Birgitta K(o|¨)nig-Ries,Kia Makki.Research Direction for Developing an Infrastructure for Mobile & Wireless Systems.Consensus Report of the NSF Workshop,2001.
[25]H.D.Chon,D.Agrawal,and A.E.Abbadi.Storage and Retrieval of Moving Objects.In Proceedings of the 2nd International Conference on Mobile Data Management (MDM),2001.
[26]Ouri Wolfson and Bo Xu.Moving Objects Databases:Issues and Solutions.In Proceedings of International Conference on Scientific and Statistical Database Management(SSDBM),1998.
[27]Y Manolopoulos,A.Nanopoulos,and AN.Papadopoulos.R-trees Have Grown Everywhere.ACM Computing Surveys,2003.
[28]廖巍,熊伟,景宁,陈宏盛.移动对象索引技术研究进展.计算机科学.33(8):166-169,2006.
[29]R.Laurini and D.Thomson.Fundamentals of Spatial Information Systems.Academic Press,London,1992.
[30]Shashi Shekhar and Sanjay Chawla.Spatial Database:A Tour.Pearson Education,2003.
[31]Guttman.R-Trees:A Dynamic Index Structure for Spatial Searching.In Proceedings of the ACM Intentional Conference on Management of Data(SIGMOD),pages 47-57,1984.
[32]N.Beckmann,H.P.Kriegel,R.Schneider and B.Seeger.The R*-tree:An Efficient and Robust Method for Points and Rectangles.In Proceeding of the ACM Intentional Conference on Management of Data(SIGMOD),pages 322-331,1990.
[33]S.Berchtold,D.A.Keim and H.P.Kriegel.The X-tree:An Index Structure for High-Dimensional Data.In Proceeding of the 22nd International Conference on Very Large Databases(VLDB),pages 28-39,1996.
[34]Nievergelt J.,Hinterberger H.,and Sevcik K.The Grid File:An Adaptable,Symmetric Multikey File Structure.ACM Transactionss on Database Systems(TODS),9(1):38-71,1984.
[35]Mohamed F.,Mokbel Thanaa,M.Ghanem,and Walid G.Aref.Spatio-temporal Access Methods.IEEE Data Engineering Bulletin,2003.
[36]Pedersen TB.Aspects of Data Modeling and Query Processing for Complex Multidimensional Data.Ph.D.Thesis,Aalborg University,Analogist,Denmark,2000.
[37]Pedersen TB,Jensen CS,and Dyreson CE.A Foundation for Capturing and Querying Complex Multidimensional Data.Information System,26(5):383-423,2001.
[38]Rafanelli M.and Shoshani A.STORM:A Statistical Object Representation Model.In Proceedings of the 5th International Conference on Statistical and Scientific Database Management(SSDBM),pages 14-29,1990.
[39]0.Wolfson,L.Jiang,A.P.Sistla,S.Chamberlain,and M.Deng.Updating and Querying Databases that Track Mobile Units.Distributed and Parallel Databases,7(6):257-387,1998.
[40]Pfoser D.and Jensen,C.S.Capturing the Uncertainty of Moving Objects Representations.In Proceedings of the 12th International Conference on Scientific and Statistical Database Management(SSDBM),2000.
[41]Pedersen,T.B.,Jensen,C.S.,and Dyreson C.E.Supporting Imprecision in Multidimensional Databases Using Granularities.In Proceedings of the 11th International Conference on Scientific and Statistical Database Management(SSDBM),pages 90-101,1999.
[42]张明波,陆峰,申排伟,程昌秀.R树家族的演变和发展.计算机学报.28(3):289-300,2005.
[43]X.Xu,J.Han and W.Lu.RT-Tree:An Improved R-Tree Indexing Structure for Temporal Spatial Databases.In Proceedings of the International Symposium on Spatial Data Handling(SDH),1990
[44]D.B.Lomet and B.Salzberg.Access Methods for Multiversion Data.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),pages 315-324,1989.
[45]Y.Theodoridis,M.Vazirgiannis,and T.Sellis.Spatio-Temporal Indexing for Large Multimedia Applications.In Proceedings of the IEEE Conference on Multimedia Computing and Systems(ICMCS),1996.
[46]S.Leutenegger,J.M.Edgington and M.A.Lopez.STR:A Simple and Efficient Algorithm for R-tree Packing.In Proceedings of the 13th IEEE Conference on Data Engineering(ICDE),pages 497-506,1997.
[47]M.A.Nascimento and J.R.O.Silva.Towards Historical R-trees.In Proceedings of the ACM Symposium on Applied Computing(SAC),1998.
[48]Y.Tao and D.Papadias.MV3R-Tree:A Spatio-Temporal Access Method for Timestamp and Interval Queries.In Proceedings of the International Conference on Very Large Databases(VLDB),2001.
[49]Y.Tao and D.Papadias.Efficient Historical R-trees.In Proceedings of the International Conference on Scientific and Statistical Database Management(SSDBM),pages 223-232,2001.
[50]G.Kollios,V.J.Tsotras,D.Gunopulos,A.Delis,and M.Hadjieleftheriou.Indexing Animated Objects Using Spatiotemporal Access Methods.IEEE Transactions on Knowledge and Data Engineering(TKDE),13(5):758-777,2001.
[51]V.P.Chakka,A.Everspaugh,and J.M.Patel.Indexing Large Trajectory Data Sets with SETI.In Proceedings of CIDR 2003.
[52]Z.Song and N.Roussopoulos.SEB-tree:An Approach to Index Continuously Moving Objects.In Proceedings of the International Conference on Mobile Data Management (MDM),2003.
[53]D.Pfoser,C.S.Jensen,and Y.Theodoridis.Novel Approaches in Query Processing for Moving Object Trajectories.In Proceedings of the International Conference on Very Large Databases(VLDB),pages 395-406,2000.
[54]M.A.Nascimento,J.R.O.Silva,and Y.Theodoridis.Evaluation of Access Structures for Discretely Moving Points.In Proceedings of the International workshop on Spatio-temporal Database Management(STDBM),1999.
[55]D.Kwon,S.Lee,and S.Lee.Indexing the Current Positions of Moving Objects Using the Lazy Update R-tree.In Proceedings of the International Conference on Mobile Data Management(MDM),2002.
[56]M.Lee,W.Hsu,C.Jensen,B.Cui,and K.Teo.Supporting Frequent Updates in R-Trees:A Bottom-Up Approach.In Proceedings of the International Conference on Very Large Databases(VLDB),2003.
[57]Z.Song and N.Roussopoulos.Hashing Moving Objects.In Proceedings of the International Conference on Mobile Data Management(MDM),2001.
[58]J.Tayeb,O.Ulusoy,and O.Wolfson.A Quadtree-Based Dynamic Attribute Indexing Method.The Computer Journal,1998.
[59]Christian S.Jensen,Dan Lin,and Beng Chin Ooi.Query and Update Efficient B+-tree Based Indexing of Moving Objects.In Proceedings of the International Conference on Very Large Databases(VLDB),2004.
[60]B.Moon,H.V.Jagadish,C.Faloutsos,and J.H.Saltz.Analysis of the Clustering Properties of the Hilbert Space-Filling Curve.IEEE Transactions on Knowledge and Data Engineering(TKDE),13(1):124-141,2001.
[61]G.Kollios,D.Gunopulos,and V.J.Tsotras.On Indexing Mobile Objects.In Proceedings of A CM PODS 1999.
[62]H.D.Chon,D.Agrawal,and A.E.Abbadi.Storage and Retrieval of Moving Objects.Proceedings of Proceedings of the International Conference on Mobile Data Management(MDM),2001.
[63]D.A.White and R.Jain.Similarity.Indexing with the SS-tree.In Proceedings of the International Conference on Data Engineering(1CDE),pages 516-523,1996.
[64]K.Porkaew,I.Lazaridis,and S.Mehrotra.Querying Mobile Objects in Spatio-Temporal Databases.In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases(SSTD),pages 59-78,2001.
[65]Jignesh M.,Patel Yun,Chen V.,and Prasad Chakka.STRIPES:An Efficient Index for Predicted Trajectories.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),2004.
[66]S.Saltenis,C.S.Jensen,S.T.Leutenegger,and M.A.Lopez.Indexing the Positions of Continuously Moving Objects.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),2000.
[67]Tao,Y.,Papadias D.and Sun,J.The TPR*-Tree:An Optimized Spatio-Temporal Access Method for Predictive Queries.In Proceedings of the International Conference on Very Large Databases(VLDB),2003.
[68]S.Prabhakar,Y.Xia,D.V.Kalashnikov,W.G.Aref,and S.E.Hambrusch.Query Indexing and Velocity Constrained Indexing:Scalable Techniques for Continuous Queries on Moving Objects.IEEE Transactions on Computers,2002.
[69]C.M.Procopiuc,P.K.Agarwal,and S.Har-Peled.STAR-Tree:An Efficient Self-Adjusting Index for Moving Objects..In Proceedings of the Workshop on Alg.Eng.and Experimentation,ALENEX,pages 178-193,Jan.2002.
[70]M.Cai and P.Revesz,Parametric R-Tree:An Index Structure for Moving Objects.In Proceedings of the International Conference on Management of Data(COMAD),2000.
[71]S.Saltenis and C.S.Jensen.Indexing of Moving Objects for Location-Based Services.In Proceedings of the International Conference on Data Engineering(1CDE),2002.
[72]Y Tao,C Faloutsos,D Papadias,and B Liu.Prediction and Indexing of Moving Objects with Unknown Motion Patterns.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),2004.
[73]A.K.Agarwal,L.Arge,and J.Ericskon.Indexing moving points.In Proceedings of ACM PODS 2000.
[74]Hae Don Chon,Divyakant Agrawal,and Amr El Abbadi.Data Management for Moving Objects.In Proceeding of International Telematics and LBS Workshop,2003.
[75]Jimeng Sun,Dimitris Papadias,Yufei Tao,Bin Liu.Querying about the Past,the Present,and the Future in Spatio-Temporal Databases.In Proceedings of the International Conference on Data Engineering(ICDE),2004.
[76]Shekhar S.and Liu D.CCAM:A Connectivity-Clustered Access Method for Networks and Network Computations.IEEE Transactions on Knowledge and Data Engineering (TKDE),19(1):102-119,1997.
[77]Huang Y.,Jing N.,and Rundensteiner,E.Integrated Query Processing Strategies for Spatial Path Queries.In Proceedings of the International Conference on Data Engineering(1CDE),1997.
[78]Yufei Tao and Papadias D.Time-Parameterized Queries in Spatio-Temporal Databases.In Proceedings of the ACM International Conference on Management of Data (SIGMOD),2002.
[79]Jun Zhang,Manli Zhu,Dimitirs Papadias,Yufei Tao,and Dik Lun Lee.Location-based Spatial Queries.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),2003.
[80]F.Korn and S.Muthukrishnan.Influence Sets Based on Reverse Nearest Neighbor Queries.In Proceedings of the ACM lnternational Conference on Management of Data (SIGMOD),pages 201-212,2000.
[81]Roussopoulos N.and Kelly S.Vincent F.Nearest Neighbor Queries.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),1995.
[82]Papadoulos and Y.Manolopoulos.Performance of Nearest Neighbor Queries in R-trees.In Proceedings of International Conference on Database Theory(1CDT),pages 394-408,1997.
[83]K.L.Cheung and A.W.fu.Enhanced Nearest Neighbor Search on the R-tree.ACM SIGMOD Record,27(3):16-21,1998.
[84]H.Samet,and G.Hjaltason.Distance Browsing in Spatial Databases.ACM Transactions on Database Systems(TODS),24(2):265-318,1999.
[85]Zheng B.and Lee D.Semantic Caching in Location Dependent Query Processing.In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases(SSTD),2001.
[86]Okabe A.,Boots B.,Sugihara K.,and Chiu S.Spatial Tessellations:Concepts and Applications of Voronoi Diagrams,John Wildy,2000.
[87]Song,Z.and Roussopoulos N.K-Nearest Neighbor Search for Moving Query Point.In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases(SSTD),2001.
[88]Tao Y.,Papadias D.,and Shen Q.Continuous Neighbor Search.In Proceedings of the International Conference on Very Large Databases(VLDB),2002.
[89]Rimantas Benetis,Christian S.Jensen,Gytis Karciauskas,and Simonas Saltenis.Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects.In Proceedings of the International Database Engineering and Applications Symposium (IDEAS),2002.
[90]Yufei Tao and Dimitris Papadias.Spatial Queries in Dynamic Environment.ACM Transactions on Database Systems(TODS),2003.
[91]Glenn S.Iwerks,Hanan Samet,and Kenneth P.Smith.Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates.In Proceedings of 29th International Conference on Very Large Databases(VLDB),2003.
[92]Mohamed F.Mokbel,Xiaopeng Xiong,and Walid G.Aref.SINA:Scalable Incremental Processing of ContinuousQueries in Spatiotemporal Databases.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),2004.
[93]Xiaopeng Xiong,Mohamed F.Mokbel and 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(ICDE),2005.
[94]Xiaohui Yu,Ken Q.Pu,and Nick Koudas.Monitoring k-Nearest Neighbor Queries over Moving Objects.In Proceedings of the 21st International Conference on Data Engineering(ICDE),2005.
[95]Kyriakos Mouratidis,Marios Hadjieleftherious,and Dimitris Papadias.Conceptual Partitioning:An Efficient Method for Continuous Nearest Neighbor Monitoring.In Proceedings of the ACM International Conference on Managemeni of Data(SIGMOD),2005.
[96]C.S.Jensen,J.Kolrvr,Y.B.Pedersen,and I.Timko.Nearest Neighbor Queries in Road Networks.In Proceedings of the llth ACM International Symposium on Advances in Geographic Information Systems(ACM-GIS),2003.
[97]M.Kolahdouzan and C.Shahabi.Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases.In Proceedings of 29th International Conference on Very Large Databases(VLDB),2004.
[98]D.Papadias,J.Zhang,N.Mamoulis,and Y.Tao.Query Processing in Spatial Network Databases.In Proceedings of 29th International Conference on Very Large Databases (VLDB),2003.
[99]Mohammad R.Kolahdouzan and Cyrus Shahabi.Continuous K Nearest Neighbor Queries in Spatial Network Databases.Proceedings of the International workshop on Spatio-temporal Database Management(STDBM),2004.
[100]Shahabi,C.,Kolahdouzan,M.,Sharifzadeh,M.A Road Network Embedding Technique for K Nearest Neighbor Search in Moving Object Databases.In Proceedings of the 11th ACM International Symposium on Advances in Geographic Information Systems(ACM-GIS),2002.
[101]J.Feng and T.Watanabe.A Fast Method for Continuous Nearest Target Objects Query on Road Network.In VSMM'02 pages 182-191 Sept.2002,Korea.
[102]S.Jung and S.Pramanik.An Efficient Path Computation Model for Hierarchically Structured Topological Road Maps.IEEE Transactions on Knowledge and Data Engineering(TKDE),2002.
[103]Ine's Fernando Vega Lo'pez,Richard T.Snodgrass,Spatiotemporal Aggregate Computation:A Survey.IEEE Transactions on Knowledge and Data Engineering (TKDE);17(2):271-286,2005.
[104]Y.Tao,G.Kollios,J.Considine,F.Li,and D.Papadias,Spatio-Temporal Aggregation Using Sketches.In Proceedings of the 21st International Conference on Data Engineering(ICDE),pages 214-226,2004.
[105]Yufei Tao,Dimitris Papadias,Jian Zhai,and Qing Li.Venn Sampling:A Novel Prediction Technique for Moving Objects.In Proceedings of the 21st International Conference on Data Engineering(ICDE),2005.
[106]Yufei Tao,Jimeng Sun,and Dimitris Papadias.Selectivity Estimation for Predictive Spatio-Temporal Queries.In Proceedings of the 21st International Conference on Data Engineering(ICDE),2003.
[107]Choi Y.,Chung C.Selectivity Estimation for Spatio-temporal Queries to Moving Objects.In Proceedings of the ACM lnternational Conference on Management of Data (SIGMOD),2002.
[108]Hadjieleftheriou M.,Kollios G.,and Tsotras V.Performance Evaluation of Spatio-temporal Selectivity Estimation Techniques.In Proceedings of the International Conference on Scientific and Statistical Database Management(SSDBM),2003.
[109]Dimitris Papadias,Yufei Tao,Kalnis P.,and Zhang J.Indexing Spatio-temporal Data Warehouse.In Proceedings of the 21st International Conference on Data Engineering(ICDE),2002.
[110]Y.Tao,Jimeng Sun,and Dimitris Papadias.Analysis of Predictive Spatio-Temporal Queries.ACM Transactions on Database Systems(TODS),28(4):295-336,2003.
[111]Yufei Tao,Dimitris Papadias,and X.Lian.Reverse kNN Search in Arbitrary Dimensionality.In Proceedings of 29th International Conference on Very Large Databases(VLDB),2004.
[112]Amit Singh,Hakan Ferhatosmanoglu,and Ali Saman Tosun.High Dimensional Reverse Nearest Neighbor Queries.In Proceedings of the 12th ACM International Conference on Information and knowledge Management(CI~,pages:91-98,2003.
[113]Chenyi Xia,Wynne Hsu,and Mong Li Lee.ERkNN:Efficient Reverse k-Nearest Neighbors Retrieval with Local kNN-Distance Estimation.In Proceedings of the 14th ACM International Conference on Information and knowledge Management(CIKM),pases 533-540,2005.
[114]Like Achtert,Christian B(¨)hm,and Peer Kr(o|¨)ger.Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces.In Proceedings of the ACM International Conference on Management of Data(SIGMOD),pages 515-526,2006.
[115]Man Lung Yiu,Dimitris Papadias,Nikos Mamoulis,and Yufei Tao.Reverse Nearest Neighbors in Large Graphs.IEEE Transactions on Knowledge and Data Engineering(TKDE),18(4):540-553,2006.
[116]Dimitris Papadias,Shen Q.,Yufei Tao,Mouratidis K.Group Nearest Neighbor Queries.In Proceedings of the 21st International Conference on Data Engineering (ICDE),2004.
[117]Ferhatosmanoglu H.,Stanoi I.,Agrawal D.,and Abbadi A.Constrained Nearest Neighbor Queries.In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases(SSTD),2001.
[118]G.S.Iwerks,H.Samet,and K.Smith.Maintenance of Spatial Semi-join Queries on Moving Points.Proceedings of 29th International Conference on Very Large Databases(VLDB),2004.
[119]Andrew Noske.Efficient Algorithms for Molecular Dynamics Simulations and Other Dynamic Spatial Join Queries.Ph.D.Thesis,Department of Information Technology,James Cook University,2004.
[120]熊伟,廖巍,陈宏盛,景宁.空间数据库中距离连接选择率估计方法研究.计算机学报.29(1):45-53.2006.
[121]熊伟,廖巍,张帆,景宁,陈宏盛.空间连接处理中提炼步骤地遗传优化.电子学报.34(6):1069-1073.2006.
[122]廖巍,熊伟,景宁,陈宏盛,钟志农.支持频繁更新的移动对象混合索引方法.计算机研究与发展.43(5):888-893.2006.
[123]熊伟,廖巍,陈宏盛,景宁.空间数据库主动规则行为控制研究.计算机研究与发展.43(8):888-893.2006.
[124]Http://www.census.gov/geo/www/tiger
[125]Yuni Xia,Sunil Prabhakar,Q+Rtree:Efficient Indexing for Moving Object Databases.Proceeding of 2003 International Conference on Database Systems for Advanced Applications.Pages:175-182,2003.
[126]Bin Lin and Jianwen Su.On Bulk Loading TPR-Tree.In Proceedings of the International Conference on Mobile Data Management(MDM),2004.
[127]Liaowei,Tangguifen,Jingning,and Zhongzhinong.VTPR-tree An Efficient Indexing Method for Moving Objects with Frequent Updates.In Proceedings of the International ER Workshop on Conceptual Modeling for Geographic Information Systems,(CoMoGIS),2006.
[128]廖巍,唐桂芬,景宁,钟志农.基于速度分布的移动对象混合索引方法.计算 机学报.2006,(录用).
[129]Haibo Hu,Jianliang Xu,and Dik Lun Lee.A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects.In Proceedings of the International Conference on Management of Data(SIGMOD).pages 479-490,2005.
[130]廖巍,唐桂芬,景宁,陈宏盛.基于扩展时空距离度量的连续k近邻查询方法.国防科技大学学报,2006,已投.
[131]廖巍,熊伟,王钧,景宁,钟志农.可伸缩的增量连续k邻近查询方法.软件学报.2006,(录用).
[132]Brinkhoff T.A Framework for Generating Network-based Moving Objects.Geolnformatica.(6)2:153-180,2002.
[133]Hicham G.Elmongui,Mohamed F.Mokbel,and Walid G.Aref.Spatio-temporal Histograms.In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases(SSTD),2005.
[134]Q.Zhang and X.Lin.Clustering Moving Objects for Spatio-temporal Selectivity Estimation.In Proceedings of the 15th International Conference on Australasian Database(CRPIT),pages 123-130.Australian Computer Society,2004.
[135]M.Jurgens and H.Lenz.The Ra*-Tree:An Improved R-Tree with Materialized Data for Supporting Range Queries on OLAP-Data.In Proceedings of the DEXA Workshop,1998.
[136]Tao Yufei and Dimitris Papadias.Historical Spatio-temporal Aggregation.ACM Transactions on Information Systems.(23) 1:61-102.2005.
[137]Liao Wei,Tang Guifen,Jing Ning,and Zhong Zhinong.Predicted Range Aggregate Processing in Spatio-temporal Databases.In Proceedings of the 3rd International VLDB workshop on Spatio-temporal Database Management(STDBM),2006.
[138]廖巍,唐桂芬,景宁,钟志农.面向移动对象的高效预测范围聚集查询方法.计算机研究与发展.2006,已投.