Show simple item record

dc.contributor.authorKülekçi, Muhammed Oǧuzhan
dc.contributor.authorThankachan, Sharma
dc.date.accessioned10.07.201910:49:13
dc.date.accessioned2019-07-10T19:35:46Z
dc.date.available10.07.201910:49:14
dc.date.available2019-07-10T19:35:46Z
dc.date.issued2015en_US
dc.identifier.citationKülekçi, M. O. ve Thankachan, S. V. (2015). Range selection queries in data aware space and time. Data Compression Conference içinde (73-82. ss.). Snowbird, Utah, April 07-09, 2015. https://dx.doi.org/10.1109/DCC.2015.53en_US
dc.identifier.isbn9781479984305
dc.identifier.issn1068-0314
dc.identifier.urihttps://hdl.handle.net/20.500.12511/940
dc.identifier.urihttps://dx.doi.org/10.1109/DCC.2015.53
dc.description.abstractOn a given vector X = (x<inf>1</inf>, x<inf>2</inf>, , x<inf>n</inf>) of integers, the range selection (i, j, k) query is finding the k-th smallest integer in (x<inf>i</inf>, x<inf>i+1</inf>, , x<inf>j</inf>) for any (i, j, k) such that 1 ? i ? j ? n, and 1 ? k ? j-i+1. Previous studies on the problem kept X intact and proposed data structures that occupied additional O (n. log n) bits of space over the X itself that answer the queries in logarithmic time. In this study, we replace X and encode all integers in it via a single wavelet tree by using S= n. log u + ?? logx<inf>i</inf>+o (n. log u + ??logx<inf>i</inf>) bits, where u is the number of distinct log x<inf>i</inf> values observed in X. Notice that u is at most 32 (64) for 32-bit (64-bit) integers and when x<inf>i</inf>>u, the space used for xi in the proposed data structure is less then the Elias-? coding of x<inf>i</inf>. Besides data-aware coding of X, the range selection is performed in O (log u + log x') time where x' is the k-th smallest integer in the queried range. This somewhat adaptive result interestingly achieves the range selection regardless of the size of X, and totally depends on the actual answer of the query. In summary, to the best of our knowledge, we present the first algorithm using data-aware space and time for the general range selection problem.en_US
dc.language.isoengen_US
dc.publisherInstitute of Electrical and Electronics Engineersen_US
dc.rightsinfo:eu-repo/semantics/embargoedAccessen_US
dc.subjectCompact Integer Codingen_US
dc.subjectRange Selectionen_US
dc.subjectWavelet Treeen_US
dc.titleRange selection queries in data aware space and timeen_US
dc.typeconferenceObjecten_US
dc.relation.ispartofData Compression Conferenceen_US
dc.departmentİstanbul Medipol Üniversitesi, Mühendislik ve Doğa Bilimleri Fakültesi, Biyomedikal Mühendisliği Bölümüen_US
dc.identifier.startpage73en_US
dc.identifier.endpage82en_US
dc.relation.publicationcategoryKonferans Öğesi - Uluslararası - Kurum Öğretim Elemanıen_US
dc.identifier.doi10.1109/DCC.2015.53en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record