{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:51:13Z","timestamp":1773481873048,"version":"3.50.1"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,9]]},"abstract":"<jats:p>\n            Inequality joins, which join relational tables on inequality conditions, are used in various applications. While there have been a wide range of optimization methods for joins in database systems, from algorithms such as sort-merge join and band join, to various indices such as\n            <jats:italic>B<\/jats:italic>\n            <jats:sup>+<\/jats:sup>\n            -tree,\n            <jats:italic>R<\/jats:italic>\n            <jats:sup>*<\/jats:sup>\n            -tree and Bitmap, inequality joins have received little attention and queries containing such joins are usually very slow. In this paper, we introduce fast inequality join algorithms. We put columns to be joined in sorted arrays and we use permutation arrays to encode positions of tuples in one sorted array\n            <jats:italic>w.r.t.<\/jats:italic>\n            the other sorted array. In contrast to sort-merge join, we use space efficient bit-arrays that enable optimizations, such as Bloom filter indices, for fast computation of the join results. We have implemented a centralized version of these algorithms on top of PostgreSQL, and a distributed version on top of Spark SQL. We have compared against well known optimization techniques for inequality joins and show that our solution is more scalable and several orders of magnitude faster.\n          <\/jats:p>","DOI":"10.14778\/2831360.2831362","type":"journal-article","created":{"date-parts":[[2015,9,30]],"date-time":"2015-09-30T12:16:36Z","timestamp":1443615396000},"page":"2074-2085","source":"Crossref","is-referenced-by-count":24,"title":["Lightning fast and space efficient inequality joins"],"prefix":"10.14778","volume":"8","author":[{"given":"Zuhair","family":"Khayyat","sequence":"first","affiliation":[{"name":"King Abdullah University of Science and Technology (KAUST)"}]},{"given":"William","family":"Lucia","sequence":"additional","affiliation":[{"name":"Qatar Computing Research Institute"}]},{"given":"Meghna","family":"Singh","sequence":"additional","affiliation":[{"name":"Qatar Computing Research Institute"}]},{"given":"Mourad","family":"Ouzzani","sequence":"additional","affiliation":[{"name":"Qatar Computing Research Institute"}]},{"given":"Paolo","family":"Papotti","sequence":"additional","affiliation":[{"name":"Qatar Computing Research Institute"}]},{"given":"Jorge-Arnulfo","family":"Quian\u00e9-Ruiz","sequence":"additional","affiliation":[{"name":"Qatar Computing Research Institute"}]},{"given":"Nan","family":"Tang","sequence":"additional","affiliation":[{"name":"Qatar Computing Research Institute"}]},{"given":"Panos","family":"Kalnis","sequence":"additional","affiliation":[{"name":"King Abdullah University of Science and Technology (KAUST)"}]}],"member":"320","published-online":{"date-parts":[[2015,9]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of Databases","author":"Abiteboul S.","year":"1995"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742797"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367920"},{"key":"e_1_2_1_4_1","first-page":"75","volume-title":"SSD","author":"B\u00f6hm C.","year":"1999"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276336"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304201"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544847"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_9_1","first-page":"443","volume-title":"VLDB","author":"DeWitt D. J.","year":"1991"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920908"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007645"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0111-3"},{"key":"e_1_2_1_13_1","volume-title":"Pearson Education","author":"Garcia-Molina H.","year":"2009"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142511"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/971697.602266"},{"key":"e_1_2_1_16_1","first-page":"562","volume-title":"VLDB","author":"Hellerstein J. M.","year":"1995"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747646"},{"key":"e_1_2_1_18_1","volume-title":"Pervasive Computing","author":"Laurila J. K.","year":"2012"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1529282.1529582"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989423"},{"key":"e_1_2_1_21_1","volume-title":"Accelerate your PostgreSQL System and Avoid the Common Pitfalls that Can Slow it Down","author":"Smith G.","year":"2010"},{"key":"e_1_2_1_22_1","first-page":"157","article-title":"Bitmap indices for data warehouses. Data Warehouses and OLAP: Concepts","volume":"5","author":"Stockinger K.","year":"2007","journal-title":"Architectures and Solutions"},{"key":"e_1_2_1_23_1","first-page":"10","volume-title":"HotCloud","author":"Zaharia M.","year":"2010"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350238"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2831360.2831362","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:28:17Z","timestamp":1672219697000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2831360.2831362"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9]]},"references-count":24,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["10.14778\/2831360.2831362"],"URL":"https:\/\/doi.org\/10.14778\/2831360.2831362","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,9]]}}}