{"id":"https://openalex.org/W3156978171","doi":"https://doi.org/10.1145/3442381.3449946","title":"Linear-Time Self Attention with Codeword Histogram for Efficient Recommendation","display_name":"Linear-Time Self Attention with Codeword Histogram for Efficient Recommendation","publication_year":2021,"publication_date":"2021-04-19","ids":{"openalex":"https://openalex.org/W3156978171","doi":"https://doi.org/10.1145/3442381.3449946","mag":"3156978171"},"language":"en","primary_location":{"id":"doi:10.1145/3442381.3449946","is_oa":true,"landing_page_url":"https://doi.org/10.1145/3442381.3449946","pdf_url":null,"source":null,"license":"cc-by","license_id":"https://openalex.org/licenses/cc-by","version":"publishedVersion","is_accepted":true,"is_published":true,"raw_source_name":"Proceedings of the Web Conference 2021","raw_type":"proceedings-article"},"type":"article","indexed_in":["arxiv","crossref"],"open_access":{"is_oa":true,"oa_status":"gold","oa_url":"https://doi.org/10.1145/3442381.3449946","any_repository_has_fulltext":true},"authorships":[{"author_position":"first","author":{"id":null,"display_name":"Yongji Wu","orcid":null},"institutions":[{"id":"https://openalex.org/I170897317","display_name":"Duke University","ror":"https://ror.org/00py81415","country_code":"US","type":"education","lineage":["https://openalex.org/I170897317"]}],"countries":["US"],"is_corresponding":true,"raw_author_name":"Yongji Wu","raw_affiliation_strings":["Duke University, USA"],"affiliations":[{"raw_affiliation_string":"Duke University, USA","institution_ids":["https://openalex.org/I170897317"]}]},{"author_position":"middle","author":{"id":null,"display_name":"Defu Lian","orcid":null},"institutions":[{"id":"https://openalex.org/I126520041","display_name":"University of Science and Technology of China","ror":"https://ror.org/04c4dkn09","country_code":"CN","type":"education","lineage":["https://openalex.org/I126520041","https://openalex.org/I19820366"]}],"countries":["CN"],"is_corresponding":false,"raw_author_name":"Defu Lian","raw_affiliation_strings":["University of Science and Technology of China, China"],"affiliations":[{"raw_affiliation_string":"University of Science and Technology of China, China","institution_ids":["https://openalex.org/I126520041"]}]},{"author_position":"middle","author":{"id":null,"display_name":"Neil Zhenqiang Gong","orcid":null},"institutions":[{"id":"https://openalex.org/I170897317","display_name":"Duke University","ror":"https://ror.org/00py81415","country_code":"US","type":"education","lineage":["https://openalex.org/I170897317"]}],"countries":["US"],"is_corresponding":false,"raw_author_name":"Neil Zhenqiang Gong","raw_affiliation_strings":["Duke University, USA"],"affiliations":[{"raw_affiliation_string":"Duke University, USA","institution_ids":["https://openalex.org/I170897317"]}]},{"author_position":"middle","author":{"id":null,"display_name":"Lu Yin","orcid":null},"institutions":[{"id":"https://openalex.org/I45928872","display_name":"Alibaba Group (China)","ror":"https://ror.org/00k642b80","country_code":"CN","type":"company","lineage":["https://openalex.org/I45928872"]}],"countries":["CN"],"is_corresponding":false,"raw_author_name":"Lu Yin","raw_affiliation_strings":["Alibaba Group, China"],"affiliations":[{"raw_affiliation_string":"Alibaba Group, China","institution_ids":["https://openalex.org/I45928872"]}]},{"author_position":"middle","author":{"id":null,"display_name":"Mingyang Yin","orcid":null},"institutions":[{"id":"https://openalex.org/I45928872","display_name":"Alibaba Group (China)","ror":"https://ror.org/00k642b80","country_code":"CN","type":"company","lineage":["https://openalex.org/I45928872"]}],"countries":["CN"],"is_corresponding":false,"raw_author_name":"Mingyang Yin","raw_affiliation_strings":["Alibaba Group, China"],"affiliations":[{"raw_affiliation_string":"Alibaba Group, China","institution_ids":["https://openalex.org/I45928872"]}]},{"author_position":"middle","author":{"id":null,"display_name":"Jingren Zhou","orcid":null},"institutions":[{"id":"https://openalex.org/I45928872","display_name":"Alibaba Group (China)","ror":"https://ror.org/00k642b80","country_code":"CN","type":"company","lineage":["https://openalex.org/I45928872"]}],"countries":["CN"],"is_corresponding":false,"raw_author_name":"Jingren Zhou","raw_affiliation_strings":["Alibaba Group, China"],"affiliations":[{"raw_affiliation_string":"Alibaba Group, China","institution_ids":["https://openalex.org/I45928872"]}]},{"author_position":"last","author":{"id":null,"display_name":"Hongxia Yang","orcid":null},"institutions":[{"id":"https://openalex.org/I45928872","display_name":"Alibaba Group (China)","ror":"https://ror.org/00k642b80","country_code":"CN","type":"company","lineage":["https://openalex.org/I45928872"]}],"countries":["CN"],"is_corresponding":false,"raw_author_name":"Hongxia Yang","raw_affiliation_strings":["Alibaba Group, China"],"affiliations":[{"raw_affiliation_string":"Alibaba Group, China","institution_ids":["https://openalex.org/I45928872"]}]}],"institutions":[],"countries_distinct_count":2,"institutions_distinct_count":7,"corresponding_author_ids":[],"corresponding_institution_ids":["https://openalex.org/I170897317"],"apc_list":null,"apc_paid":null,"fwci":1.3564,"has_fulltext":false,"cited_by_count":15,"citation_normalized_percentile":{"value":0.8277142,"is_in_top_1_percent":false,"is_in_top_10_percent":false},"cited_by_percentile_year":{"min":89,"max":99},"biblio":{"volume":null,"issue":null,"first_page":"1262","last_page":"1273"},"is_retracted":false,"is_paratext":false,"is_xpac":false,"primary_topic":{"id":"https://openalex.org/T10627","display_name":"Advanced Image and Video Retrieval Techniques","score":0.9997000098228455,"subfield":{"id":"https://openalex.org/subfields/1707","display_name":"Computer Vision and Pattern Recognition"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}},"topics":[{"id":"https://openalex.org/T10627","display_name":"Advanced Image and Video Retrieval Techniques","score":0.9997000098228455,"subfield":{"id":"https://openalex.org/subfields/1707","display_name":"Computer Vision and Pattern Recognition"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}},{"id":"https://openalex.org/T10203","display_name":"Recommender Systems and Techniques","score":0.9988999962806702,"subfield":{"id":"https://openalex.org/subfields/1710","display_name":"Information Systems"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}},{"id":"https://openalex.org/T11714","display_name":"Multimodal Machine Learning Applications","score":0.9962999820709229,"subfield":{"id":"https://openalex.org/subfields/1707","display_name":"Computer Vision and Pattern Recognition"},"field":{"id":"https://openalex.org/fields/17","display_name":"Computer Science"},"domain":{"id":"https://openalex.org/domains/3","display_name":"Physical Sciences"}}],"keywords":[{"id":"https://openalex.org/keywords/histogram","display_name":"Histogram","score":0.5752999782562256},{"id":"https://openalex.org/keywords/codebook","display_name":"Codebook","score":0.5583000183105469},{"id":"https://openalex.org/keywords/code-word","display_name":"Code word","score":0.5335000157356262},{"id":"https://openalex.org/keywords/vector-quantization","display_name":"Vector quantization","score":0.49799999594688416},{"id":"https://openalex.org/keywords/sequence","display_name":"Sequence (biology)","score":0.49309998750686646},{"id":"https://openalex.org/keywords/centroid","display_name":"Centroid","score":0.4699999988079071},{"id":"https://openalex.org/keywords/hash-function","display_name":"Hash function","score":0.44449999928474426},{"id":"https://openalex.org/keywords/quadratic-equation","display_name":"Quadratic equation","score":0.41850000619888306},{"id":"https://openalex.org/keywords/pattern-recognition","display_name":"Pattern recognition (psychology)","score":0.4092000126838684}],"concepts":[{"id":"https://openalex.org/C41008148","wikidata":"https://www.wikidata.org/wiki/Q21198","display_name":"Computer science","level":0,"score":0.7181000113487244},{"id":"https://openalex.org/C53533937","wikidata":"https://www.wikidata.org/wiki/Q185020","display_name":"Histogram","level":3,"score":0.5752999782562256},{"id":"https://openalex.org/C127759330","wikidata":"https://www.wikidata.org/wiki/Q637416","display_name":"Codebook","level":2,"score":0.5583000183105469},{"id":"https://openalex.org/C153207627","wikidata":"https://www.wikidata.org/wiki/Q863873","display_name":"Code word","level":3,"score":0.5335000157356262},{"id":"https://openalex.org/C199833920","wikidata":"https://www.wikidata.org/wiki/Q612536","display_name":"Vector quantization","level":2,"score":0.49799999594688416},{"id":"https://openalex.org/C2778112365","wikidata":"https://www.wikidata.org/wiki/Q3511065","display_name":"Sequence (biology)","level":2,"score":0.49309998750686646},{"id":"https://openalex.org/C154945302","wikidata":"https://www.wikidata.org/wiki/Q11660","display_name":"Artificial intelligence","level":1,"score":0.47600001096725464},{"id":"https://openalex.org/C146599234","wikidata":"https://www.wikidata.org/wiki/Q511093","display_name":"Centroid","level":2,"score":0.4699999988079071},{"id":"https://openalex.org/C99138194","wikidata":"https://www.wikidata.org/wiki/Q183427","display_name":"Hash function","level":2,"score":0.44449999928474426},{"id":"https://openalex.org/C129844170","wikidata":"https://www.wikidata.org/wiki/Q41299","display_name":"Quadratic equation","level":2,"score":0.41850000619888306},{"id":"https://openalex.org/C153180895","wikidata":"https://www.wikidata.org/wiki/Q7148389","display_name":"Pattern recognition (psychology)","level":2,"score":0.4092000126838684},{"id":"https://openalex.org/C80444323","wikidata":"https://www.wikidata.org/wiki/Q2878974","display_name":"Theoretical computer science","level":1,"score":0.4052000045776367},{"id":"https://openalex.org/C28855332","wikidata":"https://www.wikidata.org/wiki/Q198099","display_name":"Quantization (signal processing)","level":2,"score":0.4018000066280365},{"id":"https://openalex.org/C136197465","wikidata":"https://www.wikidata.org/wiki/Q1729295","display_name":"Variety (cybernetics)","level":2,"score":0.38769999146461487},{"id":"https://openalex.org/C152565575","wikidata":"https://www.wikidata.org/wiki/Q1124538","display_name":"Conditional random field","level":2,"score":0.33799999952316284},{"id":"https://openalex.org/C11413529","wikidata":"https://www.wikidata.org/wiki/Q8366","display_name":"Algorithm","level":1,"score":0.33570000529289246},{"id":"https://openalex.org/C125411270","wikidata":"https://www.wikidata.org/wiki/Q18653","display_name":"Encoding (memory)","level":2,"score":0.3089999854564667},{"id":"https://openalex.org/C2776036281","wikidata":"https://www.wikidata.org/wiki/Q48769818","display_name":"Constraint (computer-aided design)","level":2,"score":0.3059000074863434},{"id":"https://openalex.org/C108010975","wikidata":"https://www.wikidata.org/wiki/Q500094","display_name":"Pruning","level":2,"score":0.29820001125335693},{"id":"https://openalex.org/C82687282","wikidata":"https://www.wikidata.org/wiki/Q66221","display_name":"Auxiliary memory","level":2,"score":0.2913999855518341},{"id":"https://openalex.org/C165064840","wikidata":"https://www.wikidata.org/wiki/Q1321061","display_name":"Matching (statistics)","level":2,"score":0.2904999852180481},{"id":"https://openalex.org/C193319292","wikidata":"https://www.wikidata.org/wiki/Q272172","display_name":"Hamming distance","level":2,"score":0.2815999984741211},{"id":"https://openalex.org/C124101348","wikidata":"https://www.wikidata.org/wiki/Q172491","display_name":"Data mining","level":1,"score":0.2777999937534332},{"id":"https://openalex.org/C2780801425","wikidata":"https://www.wikidata.org/wiki/Q5164392","display_name":"Construct (python library)","level":2,"score":0.27390000224113464},{"id":"https://openalex.org/C2777402240","wikidata":"https://www.wikidata.org/wiki/Q6783436","display_name":"Masking (illustration)","level":2,"score":0.2727000117301941},{"id":"https://openalex.org/C127705205","wikidata":"https://www.wikidata.org/wiki/Q5748245","display_name":"Heuristics","level":2,"score":0.2703000009059906},{"id":"https://openalex.org/C9652623","wikidata":"https://www.wikidata.org/wiki/Q190109","display_name":"Field (mathematics)","level":2,"score":0.26919999718666077},{"id":"https://openalex.org/C2780762811","wikidata":"https://www.wikidata.org/wiki/Q1784941","display_name":"Cosine similarity","level":3,"score":0.2621000111103058},{"id":"https://openalex.org/C3018263672","wikidata":"https://www.wikidata.org/wiki/Q1296251","display_name":"Efficient algorithm","level":2,"score":0.25999999046325684},{"id":"https://openalex.org/C78548338","wikidata":"https://www.wikidata.org/wiki/Q2493","display_name":"Data compression","level":2,"score":0.25780001282691956},{"id":"https://openalex.org/C74270461","wikidata":"https://www.wikidata.org/wiki/Q1625299","display_name":"Locality-sensitive hashing","level":4,"score":0.2556999921798706}],"mesh":[],"locations_count":2,"locations":[{"id":"doi:10.1145/3442381.3449946","is_oa":true,"landing_page_url":"https://doi.org/10.1145/3442381.3449946","pdf_url":null,"source":null,"license":"cc-by","license_id":"https://openalex.org/licenses/cc-by","version":"publishedVersion","is_accepted":true,"is_published":true,"raw_source_name":"Proceedings of the Web Conference 2021","raw_type":"proceedings-article"},{"id":"pmh:oai:arXiv.org:2105.14068","is_oa":true,"landing_page_url":"http://arxiv.org/abs/2105.14068","pdf_url":"https://arxiv.org/pdf/2105.14068","source":{"id":"https://openalex.org/S4306400194","display_name":"arXiv (Cornell University)","issn_l":null,"issn":null,"is_oa":true,"is_in_doaj":false,"is_core":false,"host_organization":"https://openalex.org/I205783295","host_organization_name":"Cornell University","host_organization_lineage":["https://openalex.org/I205783295"],"host_organization_lineage_names":[],"type":"repository"},"license":null,"license_id":null,"version":"submittedVersion","is_accepted":false,"is_published":false,"raw_source_name":null,"raw_type":"text"}],"best_oa_location":{"id":"doi:10.1145/3442381.3449946","is_oa":true,"landing_page_url":"https://doi.org/10.1145/3442381.3449946","pdf_url":null,"source":null,"license":"cc-by","license_id":"https://openalex.org/licenses/cc-by","version":"publishedVersion","is_accepted":true,"is_published":true,"raw_source_name":"Proceedings of the Web Conference 2021","raw_type":"proceedings-article"},"sustainable_development_goals":[],"awards":[],"funders":[],"has_content":{"pdf":false,"grobid_xml":false},"content_urls":null,"referenced_works_count":22,"referenced_works":["https://openalex.org/W2054141820","https://openalex.org/W2077815765","https://openalex.org/W2124509324","https://openalex.org/W2143462372","https://openalex.org/W2219888463","https://openalex.org/W2783272285","https://openalex.org/W2906814785","https://openalex.org/W2946567085","https://openalex.org/W2963367478","https://openalex.org/W2964045208","https://openalex.org/W2964110616","https://openalex.org/W2964926209","https://openalex.org/W2971196067","https://openalex.org/W2984100107","https://openalex.org/W2997127698","https://openalex.org/W2997154779","https://openalex.org/W3010387158","https://openalex.org/W3012754345","https://openalex.org/W3012952868","https://openalex.org/W3080292238","https://openalex.org/W3105238007","https://openalex.org/W3106129629"],"related_works":[],"abstract_inverted_index":{"Self-attention":[0],"has":[1],"become":[2],"increasingly":[3],"popular":[4],"in":[5,164],"a":[6,46,52,56],"variety":[7],"of":[8,76,97,103,122],"sequence":[9,111,140],"modeling":[10],"tasks":[11],"from":[12,25],"natural":[13],"language":[14],"processing":[15],"to":[16,19,83,173],"recommendation,":[17],"due":[18],"its":[20,32],"effectiveness.":[21],"However,":[22],"self-attention":[23,99],"suffers":[24],"quadratic":[26],"computational":[27],"and":[28,100,167,169,176],"memory":[29,179],"complexities,":[30],"prohibiting":[31],"applications":[33],"on":[34,45,136,146],"long":[35],"sequences.":[36],"Existing":[37],"approaches":[38],"that":[39,79,156],"address":[40],"this":[41],"issue":[42],"mainly":[43],"rely":[44],"sparse":[47,104],"attention":[48,117,129,162],"context,":[49],"either":[50],"using":[51],"local":[53],"window,":[54],"or":[55,64,139],"permuted":[57],"bucket":[58],"obtained":[59],"by":[60,73],"locality-sensitive":[61],"hashing":[62],"(LSH)":[63],"sorting,":[65],"while":[66,113],"crucial":[67],"information":[68],"may":[69],"be":[70],"lost.":[71],"Inspired":[72],"the":[74,95,101,110,159],"idea":[75],"vector":[77],"quantization":[78],"uses":[80],"cluster":[81],"centroids":[82],"approximate":[84],"items,":[85],"we":[86],"propose":[87],"LISA":[88,106,157],"(LInear-time":[89],"Self":[90],"Attention),":[91],"which":[92],"enjoys":[93],"both":[94,165],"effectiveness":[96],"vanilla":[98,182],"efficiency":[102],"attention.":[105],"scales":[107],"linearly":[108],"with":[109],"length,":[112],"enabling":[114],"full":[115],"contextual":[116],"via":[118],"computing":[119],"differentiable":[120],"histograms":[121],"codeword":[123],"distributions.":[124],"Meanwhile,":[125],"unlike":[126],"some":[127],"efficient":[128,161,180],"methods,":[130],"our":[131,144],"method":[132,145],"poses":[133],"no":[134],"restriction":[135],"casual":[137],"masking":[138],"length.":[141],"We":[142],"evaluate":[143],"four":[147],"real-world":[148],"datasets":[149],"for":[150],"sequential":[151],"recommendation.":[152],"The":[153],"results":[154],"show":[155],"outperforms":[158],"state-of-the-art":[160],"methods":[163],"performance":[166],"speed;":[168],"it":[170],"is":[171],"up":[172],"57x":[174],"faster":[175],"78x":[177],"more":[178],"than":[181],"self-attention.":[183]},"counts_by_year":[{"year":2025,"cited_by_count":1},{"year":2024,"cited_by_count":2},{"year":2023,"cited_by_count":9},{"year":2022,"cited_by_count":1},{"year":2021,"cited_by_count":2}],"updated_date":"2026-03-20T23:20:44.827607","created_date":"2021-04-26T00:00:00"}