{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T12:38:31Z","timestamp":1780058311228,"version":"3.54.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,8,19]],"date-time":"2017-08-19T00:00:00Z","timestamp":1503100800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61370053"],"award-info":[{"award-number":["61370053"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61572003"],"award-info":[{"award-number":["61572003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Knowl Inf Syst"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s10115-017-1092-7","type":"journal-article","created":{"date-parts":[[2017,8,19]],"date-time":"2017-08-19T11:50:53Z","timestamp":1503143453000},"page":"141-163","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Tractable queries on big data via preprocessing with logarithmic-size output"],"prefix":"10.1007","volume":"56","author":[{"given":"Jiannan","family":"Yang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hanpin","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9517-7332","authenticated-orcid":false,"given":"Yongzhi","family":"Cao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,8,19]]},"reference":[{"issue":"12","key":"1092_CR1","first-page":"1231","volume":"7","author":"Y Cao","year":"2014","unstructured":"Cao Y, Fan W, Wo T, Yu W (2014) Bounded conjunctive queries. PVLDB 7(12):1231\u20131242","journal-title":"PVLDB"},{"key":"1092_CR2","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1016\/j.ins.2014.01.015","volume":"275","author":"CP Chen","year":"2014","unstructured":"Chen CP, Zhang CY (2014) Data-intensive applications, challenges, techniques and technologies: a survey on big data. Inf Sci 275:314\u2013347","journal-title":"Inf Sci"},{"issue":"1","key":"1092_CR3","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean J, Ghemawat S (2008) MapReduce: simplified data processing on large clusters. Commun ACM 51(1):107\u2013113","journal-title":"Commun ACM"},{"issue":"5","key":"1092_CR4","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1007\/s11390-014-1473-2","volume":"29","author":"W Fan","year":"2014","unstructured":"Fan W, Huai J (2014) Querying big data: bridging theory and practice. J Comput Sci Technol 29(5):849\u2013869","journal-title":"J Comput Sci Technol"},{"key":"1092_CR5","doi-asserted-by":"crossref","unstructured":"Fan W, Li J, Wang X, Wu Y (2012) Query preserving graph compression. In: Proceedings of the ACM 2012 international conference on management of data, pp 157\u2013168","DOI":"10.1145\/2213836.2213855"},{"issue":"9","key":"1092_CR6","first-page":"685","volume":"6","author":"W Fan","year":"2013","unstructured":"Fan W, Geerts F, Neven F (2013) Making queries tractable on big data with preprocessing: through the eyes of complexity theory. PVLDB 6(9):685\u2013696","journal-title":"PVLDB"},{"key":"1092_CR7","doi-asserted-by":"crossref","unstructured":"Fan W, Geerts F, Libkin L (2014) On scale independence for querying big data. In: Proceedings of the ACM 33rd symposium on principles of database systems, pp 51\u201362","DOI":"10.1145\/2594538.2594551"},{"key":"1092_CR8","doi-asserted-by":"crossref","unstructured":"Fan W, Wang X, Wu Y (2014) Querying big graphs within bounded resources. In: Proceedings of the ACM 2014 international conference on management of data, pp 301\u2013312","DOI":"10.1145\/2588555.2610513"},{"key":"1092_CR9","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1016\/j.ins.2015.08.054","volume":"328","author":"A Fiori","year":"2016","unstructured":"Fiori A, Mignone A, Rospo G (2016) Decoclu: density consensus clustering approach for public transport data. Inf Sci 328:378\u2013388","journal-title":"Inf Sci"},{"issue":"2","key":"1092_CR10","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/s10115-015-0830-y","volume":"46","author":"A Gani","year":"2016","unstructured":"Gani A, Siddiqa A, Shamshirband S, Hanum F (2016) A survey on indexing techniques for big data: taxonomy and performance evaluation. Knowl Inf Syst 46(2):241\u2013284","journal-title":"Knowl Inf Syst"},{"issue":"03","key":"1092_CR11","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1142\/S0129626493000253","volume":"3","author":"R Greenlaw","year":"1993","unstructured":"Greenlaw R (1993) Breadth-depth search is P-complete. Parallel Process Lett 3(03):209\u2013222","journal-title":"Parallel Process Lett"},{"key":"1092_CR12","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to parallel computation: P-completeness theory","author":"R Greenlaw","year":"1995","unstructured":"Greenlaw R, Hoover HJ, Ruzzo WL (1995) Limits to parallel computation: P-completeness theory. Oxford University Press, New York"},{"issue":"2","key":"1092_CR13","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/s10115-015-0885-9","volume":"48","author":"H Hamooni","year":"2016","unstructured":"Hamooni H, Mueen A, Neel A (2016) Phoneme sequence recognition via dtw-based classification. Knowl Inf Syst 48(2):253\u2013275","journal-title":"Knowl Inf Syst"},{"key":"1092_CR14","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/j.is.2014.07.006","volume":"47","author":"IAT Hashem","year":"2015","unstructured":"Hashem IAT, Yaqoob I, Anuar NB, Mokhtar S, Gani A, Khan SU (2015) The rise of \u201cbig data\u201d on cloud computing: review and open research issues. Inf Syst 47:98\u2013115","journal-title":"Inf Syst"},{"issue":"7","key":"1092_CR15","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1145\/2611567","volume":"57","author":"HV Jagadish","year":"2014","unstructured":"Jagadish HV, Gehrke J, Labrinidis A, Papakonstantinou Y, Patel JM, Ramakrishnan R, Shahabi C (2014) Big data and its technical challenges. Commun ACM 57(7):86\u201394","journal-title":"Commun ACM"},{"key":"1092_CR16","doi-asserted-by":"crossref","unstructured":"Jung G, Gnanasambandam N, Mukherjee T (2012) Synchronous parallel processing of big-data analytics services to optimize performance in federated clouds. In: IEEE proceedings of the 5th international conference on cloud computing, pp 811\u2013818","DOI":"10.1109\/CLOUD.2012.108"},{"key":"1092_CR17","doi-asserted-by":"crossref","unstructured":"Kang U, Tong H, Sun J, Lin C, Faloutsos C (2011) Gbase: A scalable and general graph management system. In: ACM proceedings of the 17th international conference on knowledge discovery and data mining, pp 1091\u20131099","DOI":"10.1145\/2020408.2020580"},{"key":"1092_CR18","volume-title":"Big data: principles and best practices of scalable realtime data systems","author":"N Marz","year":"2015","unstructured":"Marz N, Warren J (2015) Big data: principles and best practices of scalable realtime data systems. Manning Publications Co, Greenwich"},{"issue":"6","key":"1092_CR19","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1109\/MC.2013.196","volume":"46","author":"K Michael","year":"2013","unstructured":"Michael K, Miller KW (2013) Big data: new opportunities and new challenges. Computer 46(6):22\u201324","journal-title":"Computer"},{"issue":"4","key":"1092_CR20","first-page":"21","volume":"38","author":"B Mozafari","year":"2013","unstructured":"Mozafari B, Zeng K, D\u2019Antoni L, Zaniolo C (2013) High-performance complex event processing over hierarchical data. ACM T Database Syst 38(4):21","journal-title":"ACM T Database Syst"},{"key":"1092_CR21","unstructured":"National Research Council (2013) Frontiers in massive data analysis. The National Academies Press, Washington"},{"key":"1092_CR22","unstructured":"Papadimitriou CH (2003) Computational complexity. In: Encyclopedia of computer science. Wiley, Chichester, pp 260\u2013265"},{"issue":"2","key":"1092_CR23","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s10115-011-0465-6","volume":"33","author":"E Ramentol","year":"2012","unstructured":"Ramentol E, Caballero Y, Bello R, Herrera F (2012) Smote-rsb*: a hybrid preprocessing approach based on oversampling and undersampling for high imbalanced data-sets using smote and rough sets theory. Knowl Inf Syst 33(2):245\u2013265","journal-title":"Knowl Inf Syst"},{"key":"1092_CR24","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/j.ins.2014.03.043","volume":"285","author":"S R\u00edo del","year":"2014","unstructured":"del R\u00edo S, L\u00f3pez V, Ben\u00edtez JM, Herrera F (2014) On the use of mapreduce for imbalanced big data using random forest. Inf Sci 285:112\u2013137","journal-title":"Inf Sci"},{"issue":"4","key":"1092_CR25","first-page":"22","volume":"38","author":"AD Sarma","year":"2013","unstructured":"Sarma AD, Lee H, Gonzalez H, Madhavan J, Halevy AY (2013) Consistent thinning of large geographical data for map visualization. ACM T Database Syst 38(4):22","journal-title":"ACM T Database Syst"},{"key":"1092_CR26","unstructured":"Vardi MY (1982) The complexity of relational query languages. In: Proceedings of the 14th Annual ACM Symposium on Theory of Computing, pp 137\u2013146"},{"issue":"1","key":"1092_CR27","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1109\/TKDE.2013.109","volume":"26","author":"X Wu","year":"2014","unstructured":"Wu X, Zhu X, Wu G, Ding W (2014) Data mining with big data. IEEE T Knowl Data En 26(1):97\u2013107","journal-title":"IEEE T Knowl Data En"},{"issue":"8","key":"1092_CR28","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1016\/j.jcss.2014.04.022","volume":"80","author":"C Yang","year":"2014","unstructured":"Yang C, Zhang X, Zhong C, Liu C, Pei J, Ramamohanarao K, Chen J (2014) A spatiotemporal compression based approach for efficient big data processing on cloud. J Comput Syst Sci 80(8):1563\u20131583","journal-title":"J Comput Syst Sci"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10115-017-1092-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-017-1092-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-017-1092-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T13:47:48Z","timestamp":1659361668000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10115-017-1092-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,19]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["1092"],"URL":"https:\/\/doi.org\/10.1007\/s10115-017-1092-7","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"value":"0219-1377","type":"print"},{"value":"0219-3116","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,19]]}}}