Range selection queries in data aware space and time

Basit Öğe Kaydı
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.issued2015
dc.departmentİstanbul Medipol Üniversitesi, Mühendislik ve Doğa Bilimleri Fakültesi, Biyomedikal Mühendisliği Bölümü
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.
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.53
dc.identifier.doi10.1109/DCC.2015.53
dc.identifier.endpage82
dc.identifier.isbn9781479984305
dc.identifier.issn1068-0314
dc.identifier.scopusqualityN/A
dc.identifier.startpage73
dc.identifier.urihttps://hdl.handle.net/20.500.12511/940
dc.identifier.urihttps://dx.doi.org/10.1109/DCC.2015.53
dc.identifier.wosqualityN/A
dc.indekslendigikaynakWeb of Science
dc.indekslendigikaynakScopus
dc.language.isoen
dc.publisherInstitute of Electrical and Electronics Engineers
dc.relation.ispartofData Compression Conferenceen_US
dc.relation.publicationcategoryKonferans Öğesi - Uluslararası - Kurum Öğretim Elemanı
dc.rightsinfo:eu-repo/semantics/embargoedAccess
dc.subjectCompact Integer Coding
dc.subjectRange Selection
dc.subjectWavelet Tree
dc.titleRange selection queries in data aware space and time
dc.typeConference Object

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
İsim:
kulekci, oguzhan-2015.pdf
Boyut:
229.57 KB
Biçim:
Adobe Portable Document Format
Açıklama:
Tam Metin / Full Text
İndir

Koleksiyon

Scopus İndeksli Yayınlar Koleksiyonu
Bildiri Koleksiyonu
WoS İndeksli Yayınlar Koleksiyonu