{ "info": { "author": "Kazuaki Tanida", "author_email": "", "bugtrack_url": null, "classifiers": [ "License :: OSI Approved :: MIT License", "Programming Language :: Python :: 3" ], "description": "================================\nSITQ - Learning to Hash for MIPS\n================================\n\nSITQ is a fast algorithm for approximate Maximum Inner Product Search (MIPS).\nIt can find items which are likely to maximize inner product against a query in sublinear time.\n\nBenchemark\n==========\n\nRecommendation is one of fields where SITQ can be used.\nExperiments were conducted with `MovieLens 100K Dataset` and `MovieLens 20M Dataset`.\n\nALS in `benfred/implicit `_ is used to learn vectors of items and users, where the score of \\(user, item\\) pair is computed through inner product of those vectors.\n`Precision@10` is the ratio of correct recommendations against test dataset.\n`Fetched items` are items against which inner product are computed.\nHashing algorithms are more preferable as average and standard deviation of `fetched items` are smaller.\n\nml-100k\n-------\n\n.. csv-table:: Signature length: 4, Minimum fetched items: 20\n :header: \"Name\", \"Precision\\\\@10\", \"Fetched items. Avg\", \"Fetched items. Std\"\n\n \"**SITQ**\", 0.202, 105.2, 76.6\n \"Simple-LSH\", 0.182, 496.2, 441.2\n \"ITQ\", 0.199, 131.3, 93.7\n \"LSH\", 0.156, 161.9, 94.4\n \"brute force\", 0.242, \\(1680\\)\n\nml-20m\n------\n\n.. csv-table:: Signature length: 8, Minimum fetched items: 20\n :header: \"Name\", \"Precision\\\\@10\", \"Fetched items. Avg\", \"Fetched items. Std\"\n\n \"**SITQ**\", 0.112, 96.1, 151.1\n \"Simple-LSH\", 0.122, 2158.2, 5246.6\n \"ITQ\", 0.090, 111.0, 332.9\n \"LSH\", 0.069, 531.3, 912.2\n \"brute force\", 0.151, \\(26671\\)\n\nAlgorithm\n=========\n\nSITQ is an algorithm which combines Simple-LSH [1]_ and ITQ [2]_.\n\nSimple-LSH utilizes ordinary LSH which is for cosine similarity.\nIn order to use LSH for MIPS, it converts a vector before computing its signature.\n\nLSH computes signatures through transformation matrix which is fixed.\nITQ learns transformation matrix from item vectors for better hashing.\n\nSITQ converts vectors by means of Simple-LSH, and learns transformation matrix through ITQ.\n\nExample\n=======\n\nInstall\n-------\n\n::\n\n pip install sitq\n\nGet Signature\n-------------\n\n.. code-block:: python\n\n import numpy as np\n\n from sitq import Sitq\n\n\n # Create sample dataset\n items = np.random.rand(10000, 50)\n query = np.random.rand(50)\n\n sitq = Sitq(signature_size=8)\n\n # Learn transformation matrix\n sitq.fit(items)\n\n # Get signatures for items\n item_sigs = sitq.get_item_signatures(items)\n\n # Get signature for query\n query_sig = sitq.get_query_signatures([query])[0]\n\nRetrieve items\n--------------\n\n.. code-block:: python\n\n import numpy as np\n\n from sitq import Mips\n\n\n # Create sample dataset\n items = np.random.rand(10000, 50)\n query = np.random.rand(50)\n\n mips = Mips(signature_size=8)\n\n # Learn lookup table and parameters for search\n mips.fit(items)\n\n # Find items which are likely to maximize inner product against query\n item_indexes, scores = mips.search(query, limit=10, distance=1)\n\nReferences\n----------\n\n.. [1] Neyshabur, Behnam, and Nathan Srebro. \"On symmetric and asymmetric LSHs for inner product search.\" arXiv preprint arXiv:1410.5518 (2014).\n.. [2] Gong, Yunchao, et al. \"Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval.\" IEEE Transactions on Pattern Analysis and Machine Intelligence 35.12 (2013): 2916-2929.\n\n\n", "description_content_type": "", "docs_url": null, "download_url": "", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "https://github.com/shiroyagicorp/sitq", "keywords": "MIPS,LSH,ITQ,Maximum Inner Product Search", "license": "MIT", "maintainer": "", "maintainer_email": "", "name": "sitq", "package_url": "https://pypi.org/project/sitq/", "platform": "", "project_url": "https://pypi.org/project/sitq/", "project_urls": { "Homepage": "https://github.com/shiroyagicorp/sitq" }, "release_url": "https://pypi.org/project/sitq/0.1.3/", "requires_dist": [ "numpy", "pqkmeans" ], "requires_python": "", "summary": "Learning to Hash for Maximum Inner Product Search", "version": "0.1.3" }, "last_serial": 4839436, "releases": { "0.1.0": [ { "comment_text": "", "digests": { "md5": "99f0ab211ec0af378eaa39aa9ebceb5e", "sha256": "44ee7d9213b1a1f6956ccd36774abd19d67704c2fa82868d3d875773fd193c5c" }, "downloads": -1, "filename": "sitq-0.1.0-py3-none-any.whl", "has_sig": false, "md5_digest": "99f0ab211ec0af378eaa39aa9ebceb5e", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": null, "size": 5690, "upload_time": "2019-02-18T10:13:34", "url": "https://files.pythonhosted.org/packages/c3/b0/149e4c358f9da94f183942d52a854c3daa226e092606b4e3364b6811188a/sitq-0.1.0-py3-none-any.whl" } ], "0.1.1": [ { "comment_text": "", "digests": { "md5": "7cfb1c716264f3c6a581badda283b128", "sha256": "3ab58e33d57bb9828b3e97d733a6a0fb30bac792cd16db1c63249401518b7857" }, "downloads": -1, "filename": "sitq-0.1.1-py3-none-any.whl", "has_sig": false, "md5_digest": "7cfb1c716264f3c6a581badda283b128", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": null, "size": 5700, "upload_time": "2019-02-19T00:45:47", "url": "https://files.pythonhosted.org/packages/c9/9e/605d62bca1cf86616ddb11bf13e98cc44aafe09a21b19f2ce0b955824f4a/sitq-0.1.1-py3-none-any.whl" } ], "0.1.2": [ { "comment_text": "", "digests": { "md5": "e9049c6f09abbcd061cc629e578e8599", "sha256": "3de0d897fb4a15ce81380ef215c9cab68420f93964ba9cb5c7612a2d8b6d2218" }, "downloads": -1, "filename": "sitq-0.1.2-py3-none-any.whl", "has_sig": false, "md5_digest": "e9049c6f09abbcd061cc629e578e8599", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": null, "size": 5886, "upload_time": "2019-02-19T02:12:02", "url": "https://files.pythonhosted.org/packages/a0/13/d5a80dea8844255f61c4e25300382e4c1f7c553c0d4cc11c5ad7f766f9a7/sitq-0.1.2-py3-none-any.whl" } ], "0.1.3": [ { "comment_text": "", "digests": { "md5": "0be0695189e4a2badbb63d433dc25fac", "sha256": "125e2a17a31376ab257ffa7ec68289b656201071dc9b2a363655bd62fca1ab80" }, "downloads": -1, "filename": "sitq-0.1.3-py3-none-any.whl", "has_sig": false, "md5_digest": "0be0695189e4a2badbb63d433dc25fac", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": null, "size": 5971, "upload_time": "2019-02-19T11:29:17", "url": "https://files.pythonhosted.org/packages/e3/56/0a334690383aa1c841fa32990ca5d2bbc7fd61d17d2a74624cab89433228/sitq-0.1.3-py3-none-any.whl" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "0be0695189e4a2badbb63d433dc25fac", "sha256": "125e2a17a31376ab257ffa7ec68289b656201071dc9b2a363655bd62fca1ab80" }, "downloads": -1, "filename": "sitq-0.1.3-py3-none-any.whl", "has_sig": false, "md5_digest": "0be0695189e4a2badbb63d433dc25fac", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": null, "size": 5971, "upload_time": "2019-02-19T11:29:17", "url": "https://files.pythonhosted.org/packages/e3/56/0a334690383aa1c841fa32990ca5d2bbc7fd61d17d2a74624cab89433228/sitq-0.1.3-py3-none-any.whl" } ] }