d-k-min-wise independent family of hash functions
详细信息 查看全文
- 作者：Guy Feigenblata ; b ; feigeng@cs.biu.ac.il" class="auth_mail" title="E-mail the corresponding author ; Ely Porata ; porately@cs.biu.ac.il" class="auth_mail" title="E-mail the corresponding author ; Ariel Shiftana ; shiftaa@cs.biu.ac.il" class="auth_mail" title="E-mail the corresponding author
- 关键词：min-wise hash functions ; Data streams ; Windowed data streams ; Similarity ; Rarity
- 刊名：Journal of Computer and System Sciences
- 出版年：2017
- 出版时间：March 2017
- 年：2017
- 卷：84
- 期：Complete
- 页码：171-184
- 全文大小：396 K
文摘
- class="listitem" id="list_ls0010">
- class="label">•
A framework to exponentially improve space and time of min-wise based algorithms.
- class="label">•
Gets around the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300848&_mathId=si2.gif&_user=111111111&_pii=S0022000016300848&_rdoc=1&_issn=00220000&md5=cee42811d1e042484854439744da68ac" title="Click to view the MathML source">Ω(log1/ϵ)class="mathContainer hidden">class="mathCode"> lower bound needed by min-wise hash functions.
- class="label">•
Only a constant degree of independence is required for the space and time improvements.
- class="label">•
Demonstrates how to apply the framework for similarity and rarity over data stream.