IDEAS home Printed from https://ideas.repec.org/a/spr/infosf/vyid10.1007_s10796-016-9646-x.html
   My bibliography  Save this article

Index partitioning through a bipartite graph model for faster similarity search in recommendation systems

Author

Listed:
  • Ali Cevahir

    (Rakuten Institute of Technology)

Abstract

Scalability of a recommendation system is an important factor for large e-commerce sites containing millions of products visited by millions of users. Similarity search is the core operation in recommendation systems. In this paper, we explain a framework to alleviate performance bottleneck of similarity search for very large-scale recommendation systems. The framework employs inverted index for real-time similarity search and handles dynamic updates. As the inverted index gets larger, retrieving recommendations become computationally expensive. There are various works devoted to solve this problem, such as clustering and preprocessing to compute recommendations offline. Our solution is based on bipartite graph partitioning for minimizing the affinity between entities in different partitions. Number of operations in similarity search is reduced by executing search within the closest partitions to the query. Parts are balanced, so that computational loads of partitions are almost the same, which is significant for reducing the computational cost. Sequential experiments with several different recommendation approaches and large datasets consisting of millions of users and items validate the scalability of the proposed recommendation framework. Accuracy drops only by a small factor due to partitioning, if any. Even slight improvements in recommendation accuracy are observed in our collaborative filtering experiments.

Suggested Citation

  • Ali Cevahir, 0. "Index partitioning through a bipartite graph model for faster similarity search in recommendation systems," Information Systems Frontiers, Springer, vol. 0, pages 1-16.
  • Handle: RePEc:spr:infosf:v::y::i::d:10.1007_s10796-016-9646-x
    DOI: 10.1007/s10796-016-9646-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10796-016-9646-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10796-016-9646-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Chong Ju Choi & Carla C. J. M. Millar & Caroline Y. L. Wong, 2005. "Knowledge and the State," Palgrave Macmillan Books, in: Knowledge Entanglements, chapter 0, pages 19-38, Palgrave Macmillan.
    2. Zan Huang & Daniel D. Zeng & Hsinchun Chen, 2007. "Analyzing Consumer-Product Graphs: Empirical Findings and Applications in Recommender Systems," Management Science, INFORMS, vol. 53(7), pages 1146-1164, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Zan Huang & Daniel Dajun Zeng, 2011. "Why Does Collaborative Filtering Work? Transaction-Based Recommendation Model Validation and Selection by Analyzing Bipartite Random Graphs," INFORMS Journal on Computing, INFORMS, vol. 23(1), pages 138-152, February.
    2. Christian Matt & Thomas Hess, 2016. "Product fit uncertainty and its effects on vendor choice: an experimental study," Electronic Markets, Springer;IIM University of St. Gallen, vol. 26(1), pages 83-93, February.
    3. Gediminas Adomavicius & YoungOk Kwon, 2014. "Optimization-Based Approaches for Maximizing Aggregate Recommendation Diversity," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 351-369, May.
    4. Kartik Hosanagar & Daniel Fleder & Dokyun Lee & Andreas Buja, 2014. "Will the Global Village Fracture Into Tribes? Recommender Systems and Their Effects on Consumer Fragmentation," Management Science, INFORMS, vol. 60(4), pages 805-823, April.
    5. Ali Cevahir, 2017. "Index partitioning through a bipartite graph model for faster similarity search in recommendation systems," Information Systems Frontiers, Springer, vol. 19(5), pages 1161-1176, October.
    6. Yicheng Song & Nachiketa Sahoo & Elie Ofek, 2019. "When and How to Diversify—A Multicategory Utility Model for Personalized Content Recommendation," Management Science, INFORMS, vol. 65(8), pages 3737-3757, August.
    7. Oliver Hinz & Jochen Eckert, 2010. "The Impact of Search and Recommendation Systems on Sales in Electronic Commerce," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 2(2), pages 67-77, April.
    8. Zhang, Yi-Lu & Guo, Qiang & Ni, Jing & Liu, Jian-Guo, 2015. "Memory effect of the online rating for movies," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 417(C), pages 261-266.
    9. Xiao-Bai Li & Jialun Qin, 2017. "Anonymizing and Sharing Medical Text Records," Information Systems Research, INFORMS, vol. 28(2), pages 332-352, June.
    10. Lawrence Bunnell & Kweku-Muata Osei-Bryson & Victoria Y. Yoon, 0. "RecSys Issues Ontology: A Knowledge Classification of Issues for Recommender Systems Researchers," Information Systems Frontiers, Springer, vol. 0, pages 1-42.
    11. Martinovici, A., 2019. "Revealing attention - how eye movements predict brand choice and moment of choice," Other publications TiSEM 7dca38a5-9f78-4aee-bd81-c, Tilburg University, School of Economics and Management.
    12. Joanna Sokolowska & Patrycja Sleboda, 2015. "The Inverse Relation Between Risks and Benefits: The Role of Affect and Expertise," Risk Analysis, John Wiley & Sons, vol. 35(7), pages 1252-1267, July.
    13. Jong-Seok Lee & Dan Zhu, 2012. "Shilling Attack Detection---A New Approach for a Trustworthy Recommender System," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 117-131, February.
    14. Donald R. Haurin & Stuart S. Rosenthal, 2009. "Language, Agglomeration and Hispanic Homeownership," Real Estate Economics, American Real Estate and Urban Economics Association, vol. 37(2), pages 155-183, June.
    15. Jong Won Min, 2019. "The Influence of Stigma and Views on Mental Health Treatment Effectiveness on Service Use by Age and Ethnicity: Evidence From the CDC BRFSS 2007, 2009, and 2012," SAGE Open, , vol. 9(3), pages 21582440198, September.
    16. Zhan (Michael) Shi & T. S. Raghu, 2020. "An Economic Analysis of Product Recommendation in the Presence of Quality and Taste-Match Heterogeneity," Information Systems Research, INFORMS, vol. 31(2), pages 399-411, June.
    17. Voxi Amavilah & Antonio R. Andrés, 2014. "Globalization, Peace & Stability, Governance, and Knowledge Economy," Research Africa Network Working Papers 14/012, Research Africa Network (RAN).
    18. Alwang, Jeffrey & Larochelle, Catherine & Barrera, Victor, 2017. "Farm Decision Making and Gender: Results from a Randomized Experiment in Ecuador," World Development, Elsevier, vol. 92(C), pages 117-129.
    19. Yanina Welp & Ferran Urgell & Eduard Aibar, 2007. "From Bureaucratic Administration to Network Administration? An Empirical Study on E-Government Focus on Catalonia," Public Organization Review, Springer, vol. 7(4), pages 299-316, December.
    20. Brent Hammer & Helen Vallianatos & Candace Nykiforuk & Laura Nieuwendyk, 2015. "Perceptions of healthy eating in four Alberta communities: a photovoice project," Agriculture and Human Values, Springer;The Agriculture, Food, & Human Values Society (AFHVS), vol. 32(4), pages 649-662, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:infosf:v::y::i::d:10.1007_s10796-016-9646-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.