{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,7,27]],"date-time":"2023-07-27T00:11:23Z","timestamp":1690416683227},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,8]]},"abstract":"<jats:p>Location-Based Service (LBS) is rapidly becoming the next ubiquitous technology for a wide range of mobile applications. To support applications that demand nearest-neighbor and history queries, an LBS spatial indexer must be able to efficiently update, query, archive and mine location records, which can be in contention with each other. In this work, we propose MOIST, whose baseline is a recursive spatial partitioning indexer built upon BigTable. To reduce update and query contention, MOIST groups nearby objects of similar trajectory into the same school, and keeps track of only the history of school leaders. This dynamic clustering scheme can eliminate redundant updates and hence reduce update latency. To improve history query processing, MOIST keeps some history data in memory, while it flushes aged data onto parallel disks in a locality-preserving way. Through experimental studies, we show that MOIST can support highly efficient nearest-neighbor and history queries and can scale well with an increasing number of users and update frequency.<\/jats:p>","DOI":"10.14778\/2367502.2367522","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1838-1849","source":"Crossref","is-referenced-by-count":7,"title":["MOIST"],"prefix":"10.14778","volume":"5","author":[{"given":"Junchen","family":"Jiang","sequence":"first","affiliation":[{"name":"Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongji","family":"Bao","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edward Y.","family":"Chang","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuqian","family":"Li","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/sitescontent.google.com\/mobile-2014-research. http:\/\/sitescontent.google.com\/mobile-2014-research."},{"key":"e_1_2_1_2_1","first-page":"591","volume-title":"VLDB","author":"Biveinis L.","year":"2007"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2006.105"},{"key":"e_1_2_1_4_1","volume-title":"Springer","author":"Chang E. Y.","year":"2011"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"F. Chang J. Dean S. Ghemawat W. Hsieh D. Wallach M. Burrows T. Chandra A. Fikes and R. Gruber. Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems (TOCS) 26(2):1--26 2008. 10.1145\/1365815.1365816 F. Chang J. Dean S. Ghemawat W. Hsieh D. Wallach M. Burrows T. Chandra A. Fikes and R. Gruber. Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems (TOCS) 26(2):1--26 2008. 10.1145\/1365815.1365816","DOI":"10.1145\/1365815.1365816"},{"issue":"2","key":"e_1_2_1_6_1","first-page":"1574","article-title":"A benchmark for evaluating moving object indexes","volume":"1","author":"Chen S.","year":"2008","journal-title":"PVLDB"},{"key":"e_1_2_1_7_1","first-page":"29","volume-title":"ACM SIGMOD","author":"Chen S.","year":"2008"},{"issue":"1","key":"e_1_2_1_8_1","first-page":"735","article-title":"An adaptive updating protocol for reducing moving object database workload","volume":"3","author":"Chen S.","year":"2010","journal-title":"PVLDB"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.80"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1145\/2025876.2025884","volume-title":"Proceedings of the 1st International Workshop on Mobile Location-based Service","author":"Gao Y.","year":"2011"},{"key":"e_1_2_1_11_1","first-page":"1121","volume-title":"ICDE","author":"Gedik B.","year":"2008"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-2822-7"},{"key":"e_1_2_1_13_1","first-page":"479","volume-title":"ACM SIGMOD","author":"Hu H.","year":"2005"},{"key":"e_1_2_1_14_1","first-page":"11","volume-title":"ACM SIGMOD","author":"Jain A.","year":"2004"},{"key":"e_1_2_1_15_1","first-page":"768","volume-title":"VLDB","author":"Jensen C.","year":"2004"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1054"},{"key":"e_1_2_1_17_1","unstructured":"M. Kurashige and S. Fukushima. Image converter for mapping a two-dimensional image onto a three dimensional curved surface created from two-dimensional image data Nov. 8 1994. US Patent 5 363 476. M. Kurashige and S. Fukushima. Image converter for mapping a two-dimensional image onto a three dimensional curved surface created from two-dimensional image data Nov. 8 1994. US Patent 5 363 476."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1145\/1014052.1014129","volume-title":"KDD","author":"Li Y.","year":"2004"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1145\/1071246.1071256","volume-title":"Proceedings of the 6th International Conference on Mobile Data Management","author":"Lin D.","year":"2005"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"M. Mokbel and W. Aref. Space-Filling Curves. 2008. M. Mokbel and W. Aref. Space-Filling Curves. 2008.","DOI":"10.1007\/978-0-387-35973-1_1233"},{"issue":"1","key":"e_1_2_1_21_1","first-page":"1493","article-title":"RoadTrack: scaling location updates for mobile clients on road networks with query awareness","volume":"3","author":"Pesti P.","year":"2010","journal-title":"PVLDB"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2002.1039840"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1145\/342009.335427","volume-title":"ACM SIGMOD","author":"\u0160altenis S.","year":"2000"},{"key":"e_1_2_1_24_1","first-page":"790","volume-title":"VLDB","author":"Tao Y.","year":"2003"},{"issue":"1","key":"e_1_2_1_25_1","first-page":"1186","article-title":"Workload-aware indexing of continuously moving objects","volume":"2","author":"Tzoumas K.","year":"2009","journal-title":"PVLDB"},{"issue":"4","key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1109\/MSP.2006.1657823","article-title":"A personal history of the Viterbi algorithm","volume":"23","author":"Viterbi A.","year":"2006","journal-title":"IEEE Signal Processing Magazine"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0013-2"},{"issue":"1","key":"e_1_2_1_28_1","first-page":"1198","article-title":"Effectively indexing uncertain moving objects for predictive queries","volume":"2","author":"Zhang M.","year":"2009","journal-title":"PVLDB"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2367502.2367522","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T23:56:14Z","timestamp":1690415774000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2367502.2367522"}},"subtitle":["a scalable and parallel moving object indexer with school tracking"],"short-title":[],"issued":{"date-parts":[[2012,8]]},"references-count":28,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["10.14778\/2367502.2367522"],"URL":"https:\/\/doi.org\/10.14778\/2367502.2367522","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,8]]}}}